Использование Python для решения сложных математических задач

О проекте Эйлер:

Project Euler — это серия сложных задач по математике/компьютерному программированию, для решения которых потребуется нечто большее, чем просто математическое понимание. Он был создан в 2001 году как подраздел другого веб-сайта по решению задач, mathschallenge.net. Новые задачи добавляются раз в неделю, причем большинство новых задач предлагает член сообщества PE. Цель проекта Euler — предоставить людям возможность поддерживать и улучшать свои навыки в математике, программировании и решении задач. По состоянию на 21 ноября 2019 года на сайте нужно решить 689 задач.

Начиная с проблем:

Я решил пройтись по задачам в порядке от наименее сложных к наиболее сложным (PE присваивает каждой задаче «рейтинг сложности»). Это позволило бы мне построить каждую успешно решенную проблему и сделать более сложные проблемы более управляемыми.

Проблема 1:

Чтобы решить эту проблему, я использовал оператор if внутри цикла for. Это было довольно простое решение.

Проблема 2:

Эта задача определенно сложнее, чем задача 1. К счастью, я недавно узнал о рекурсии в Python, и одним из примеров было вычисление последовательности Фибоначчи.

Вот код для вычисления значения n-го члена:

Я создал новый модуль Python для хранения всех вычислений, которые мне нужно было создать для решения задач PE, и поместил в этот новый модуль функцию для Фибоначчи. Затем я импортировал модуль с функцией Фибоначчи, чтобы мой код решения оставался чистым.

Проблема 3:

Это был первый, который действительно вызвал у меня затруднения. Чтобы решить эту проблему, мне пришлось придумать способ проверить, является ли число простым, а затем проверить, является ли это число фактором 600851475143. Для этого в модуле потребовались две отдельные функции: одна для проверки того, является ли заданное число простым, и один, чтобы проверить все возможные факторы.

Это две функции; isprime проверяет все возможные условия, которые сделают число не простым, а max_prime_factor перебирает диапазон возможных факторов и помещает эти числа в функцию isprime. Если число является простым и является множителем данного числа, функция max_prime_factor установит это число как возвращаемое значение максимального простого числа. Поскольку итерация идет в порядке возрастания, это означает, что последний найденный простой множитель будет иметь максимальное значение. В этом случае максимальный простой делитель 600851475143 равен 6857.

Проблема 4:

Эта проблема была самой сложной до сих пор. Чтобы решить эту проблему, мне пришлось использовать вложенный цикл for. Сначала я думал, что смогу выполнить итерацию в обратном порядке и просто взять первое решение. К сожалению, мне не удалось заставить этот подход работать. В конце концов, я выполнил итерацию в обычном режиме и создал переменную, которая будет присвоена самому высокому найденному палиндрому.

В функции check_for_palindrome мне пришлось взять ввод (целое число) и преобразовать его в строку. Затем я сравнил результат с его противоположностью. Если строка совпадала с перевернутой строкой, функция возвращала значение true.

Проблема 5:

У этой задачи было очень простое, хотя и некрасивое решение: для каждого числа, начинающегося с 2520, проверить, делится ли оно на все числа от 1 до 20.

Проблема 14:

С этого момента я буду выделять только те проблемы, которые были особенно трудными или интересными.

Задача 14 была интересна тем, что требовала новой функции для вычисления последовательности.

Потребовалось несколько творческих циклов, но в целом создать функцию было несложно. Как только функция построена, все, что мне нужно было сделать, это включить функцию в цикл для перебора всех значений до 1 миллиона.

Задача 17:

Задача 17 представляла интересную задачу. Самое быстрое решение требовало от меня найти систему для кодирования заданного числа, затем перебрать все возможные числа и найти общее количество букв.

В этом фрагменте «S» — это список, содержащий количество букв от «Один» до «Девятнадцать», «D» содержит количество букв, кратное 10, от «Десять» до «Девяносто», «Н» представляет «Сотня» и «Т» означают «Тысячу».

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

Вывод:

До сих пор Project Euler бросал вызов моим навыкам программирования и математики. Хотя ни одна из проблем не заняла у меня слишком много времени, каждая из них представляла собой новый набор проблем, требующих творческого решения. PE — очень хороший инструмент для поддержания ваших навыков программирования, и он даже научил меня некоторым новым хорошим приемам. Я буду добавлять к этому, поскольку я продолжаю работать над списком проблем.