Три кадра решений Project Euler, написанных на языке программирования D

Содержание

  1. Введение
  2. Получение даже
  3. В расцвете сил
  4. Жить по-крупному
  5. Последние мысли
  6. Сноски

Введение

Project Euler¹ — это веб-сайт, предлагающий математические головоломки, которые обычно решаются с помощью компьютерного программирования. У них более миллиона зарегистрированных пользователей, которые в совокупности представили более двенадцати миллионов правильных решений своих головоломок². Если посмотреть на GitHub, можно обнаружить 40 846 репозиториев, относящихся к «проекту Эйлера»³, и кажется, что очень немногие из них, если вообще есть, имеют решения, реализованные на языке программирования D.⁴

Некоторое время назад я решил выучить язык D, и, поскольку решений Project Euler, написанных на языке D, не так много, я решил воспользоваться этой возможностью и опубликовать решения, написанные на этом языке. В этой статье я расскажу о трех загадках, которые показались мне интересными, и о своих решениях для них.

Квитирование: четная последовательность Фибоначчи

«Каждый новый член в последовательности Фибоначчи генерируется путем добавления двух предыдущих членов. Начиная с 1 и 2, первые 10 членов будут:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Рассмотрев члены последовательности Фибоначчи, значения которых не превышают четырех миллионов, найдите сумму членов с четными значениями». (Проект Эйлер)

Таким образом, эта головоломка состоит в том, чтобы ввести читателя, который раньше не программировал на D, в «канавку» программирования на D, познакомив его с тем, как D использует элементарные понятия программирования, такие как условная логика и циклы.

Я решил эту проблему, определив статический массив⁵ “fibonacci” для обработки суммирования двух предыдущих чисел и динамический массив⁶ “even_fibonacci” для хранения четных чисел Фибоначчи. Я реализовал простой цикл do…while, похожий на тот, что используется в C++ или Java, с условием запуска базовой логики до тех пор, пока сумма ранее вычисленных чисел Фибоначчи не станет больше или равна 3 999 999.

«Основная логика» включает добавление того, что находится в массиве Фибоначчи, проверку на четность (это можно выяснить, вычислив число n по формуле: n mod 2 и проверив, не равно ли оно нулю), добавление его к список (язык D добавляет объекты в списки, такие как list ~= object ) и обновление двух чисел в массиве fibonacci самым верхним числом и вновь вычисленным числом.

Это было довольно легко, на мой взгляд.

В расцвете сил: 10001-й расцвет

«Перечислив первые шесть простых чисел: 2, 3, 5, 7, 11 и 13, мы увидим, что 6-е простое число равно 13.

Что такое 10 001-е простое число?» (Проект Эйлер)

Поэтому я хотел продемонстрировать это, потому что мне нужно было перенести код с хорошего веб-сайта, посвященного компьютерным наукам, под названием GeeksForGeeks⁷, на котором была статья, посвященная решету Эратосфена, реализованному на Python⁸.

В моем случае Решето Эратосфена включает в себя создание массива из bool типов данных, заполненных true значениями, итерацию по списку, увеличивающуюся на текущую позицию в массиве, и маркировку составных индексов как false.

Это видео от Khan Academy и Art of the Problem описывает решето намного лучше, чем я когда-либо мог:

Это было немного сложно, но я смог портировать скрипт Python во что-то, что язык D может понять и выполнить:

Жизнь на широкую ногу: самый большой продукт в серии

«Четыре соседние цифры тысячезначного числа, имеющие наибольшее произведение, равны 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843 [... чик ...]

05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Найдите тринадцать соседних цифр в 1000-значном числе, которые имеют наибольшее произведение. Какова ценность этого продукта?» (Проект Эйлер)

Так что этот был интересен. Решить это было не так сложно, но довольно утомительно. Под этим я подразумеваю, что решение не было интеллектуально сложным, скорее в нем была ошибка, настолько тривиальная, что мне пришлось спросить StackOverflow, что не так с моим кодом.

Оказалось, что головоломка «[l]самый большой продукт в серии» дала число, которое было слишком большим для типа данных int (в шестнадцатеричном формате: 0x57994b000), как указал кто-то из StackOverflow.⁹ Поэтому я решил пойти с тип long, поскольку он имеет размер 64 бита:

Последние мысли

Опять же, это всего лишь описание некоторых математических вещей, которые можно делать с языком D. Попробуйте принять вызов, который может предложить Project Euler, и посмотрите, чему вы можете научиться.

Вот что у меня есть на данный момент с точки зрения решений:



Alekseyyy/SNHU
Project Euler — это веб-сайт, предлагающий математические головоломки, которые обычно можно решить с помощью компьютерного программирования. Мой…github.com



Благодарности

Я хотел бы поблагодарить прекрасных людей на GeeksForGeeks и StackOverflow за публикацию статей и наличие сообщества полезных и умных инженеров-программистов, которые прямо или косвенно помогают мне в моей работе.

Сноски

  1. https://projecteuler.net/
  2. По состоянию на 4 июля 2021 г.: https://projecteuler.net/statistics.
  3. По состоянию на 4 июля 2021 г.: https://archive.today/aWySX.
  4. https://dlang.org/
  5. https://tour.dlang.org/tour/en/basics/arrays
  6. Там же.
  7. https://www.geeksforgeeks.org/
  8. Программа Python для решета Эратосфена. КомпьютерщикиДляГиков. Получено 4 июля 2021 г.: https://www.geeksforgeeks.org/python-program-for-sieve-of-eratosthenes/
  9. Ветка StackOverflow: https://stackoverflow.com/questions/68245264/inconsintent-behaviour-with-computation-of-greatest-product-given-n-adjacent-d