Использование 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 — очень хороший инструмент для поддержания ваших навыков программирования, и он даже научил меня некоторым новым хорошим приемам. Я буду добавлять к этому, поскольку я продолжаю работать над списком проблем.
