Подсказки для Euler проблемы проекта № 78
Я еще не видел рекурсии, таким образом, здесь идет...
import re
r = re.compile("[^0-9a-zA-Z]")
def is_pal(s):
def inner_pal(s):
if len(s) == 0:
return True
elif s[0] == s[-1]:
return inner_pal(s[1:-1])
else:
return False
r = re.compile("[^0-9a-zA-Z]")
return inner_pal(r.sub("", s).lower())
4 ответа
Википедия может вам здесь помочь. Я предполагаю, что решение, которое у вас уже есть, представляет собой рекурсию, подобную той, что описана в разделе «промежуточная функция». Это можно использовать для нахождения решения проблемы Эйлера, но это не быстро.
Намного лучший способ - использовать рекурсию, основанную на теореме о пятиугольных числах в следующем разделе. Доказательство этой теоремы непросто, поэтому я не думаю, что авторы задачи ожидают, что вы сами придумаете теорему. Скорее, это одна из проблем, по которой они ожидают некоторого литературного поиска.
Решали ли вы задачи 31 или 76 ? Они образуют красивый набор, который каждый раз является обобщением одной и той же базовой задачи. Ответ на простые вопросы может дать вам представление о решении для 78.
вот несколько советов:
Делимость на миллион - это не то же самое, что просто быть больше чем один миллион. 1 миллион = 1 000 000 = 10 ^ 6 = 2 ^ 6 * 5 ^ 6.
Итак, вопрос состоит в том, чтобы найти наименьшее n, чтобы множители p (n) содержали шесть двоек и шесть пятерок.
Эта проблема действительно требует найти первый член в последовательности целочисленных разделов, который делится на 1 000 000.
Разделение целого числа n - это один из способов описать, сколькими способами можно сложить сумму положительных целых чисел ≤ n, чтобы получить равное n, независимо от порядка. Функция p (n) используется для обозначения количества разделов для n. Ниже мы показываем наши 5 «монет» в виде дополнений для оценки 7 разделов, то есть p (5) = 7.
5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1
Мы используем производящую функцию для создания ряда, пока не найдем требуемое n. Для производящей функции требуется не более 500 так называемых обобщенных пятиугольных чисел, задаваемых как n (3n - 1) / 2 с 0, ± 1, ± 2, ± 3…, первые несколько из которых - 0, 1, 2, 5. , 7, 12, 15, 22, 26, 35,… (A001318 Слоана).
У нас есть следующая производящая функция, которая использует наши пятиугольные числа в качестве показателей:
1 - q - q ^ 2 + q ^ 5 + q ^ 7 - q ^ 12 - q ^ 15 + q ^ 22 + q ^ 26 + ...
в моем блоге на blog.dreamshire.com есть программа на Perl, которая решает эту проблему менее чем за 10 секунд.