Использование рекурсии более 1000 раз
Я новичок в программировании на Python(мой 1 язык программирования). Решал задачу №12 из Проекта Эйлера. Я использовал рекурсию в функции, но к сожалению, чтобы решить задачу, придётся использовать рекурсию более 1000 раз. Хотел бы узнать, как решить эту задачу по-прежнему используя рекурсию, для того чтобы знать об этом в будущем. Как можно улучшить код и что вы думаете о моих названиях переменных и функции? Вот так звучит задача : Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-ое треугольное число равно 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, . Перечислим делители первых семи треугольных чисел: 1: 1 3: 1, 3 6: 1, 2, 3, 6 10: 1, 2, 5, 10 15: 1, 3, 5, 15 21: 1, 3, 7, 21 28: 1, 2, 4, 7, 14, 28 Как мы видим, 28 — первое треугольное число, у которого более пяти делителей. Каково первое треугольное число, у которого более пятисот делителей? Вот мой код:
def tringle_number(x): if x == 1: return 1 else: return x + tringle_number(x-1) for i in range(1, 900): a.append(tringle_number(i)) print(a) need = 0 all_number = [1] count = 0 for item in a: number = 0 for j in range(1, 100000): if item % j == 0: count = j number += 1 if number == 100: for items in all_number: need += 1 if need == 1: all_number.append(item) else: continue else: continue print(all_number[1]) Отслеживать
543 5 5 серебряных знаков 14 14 бронзовых знаков
задан 18 дек 2020 в 18:56
Как увеличить размер стека python
stefdasca → Click here if you want to know your future CF rating [Part 2]
LucaLucaM → Most helpful person on CF in 2023
_ _asm__ → Most annoying person on CF in 2023
MikeMirzayanov → Polygon: AI-Powered Automatic Tips
Blinov_Artemii → Bullying on Codeforces
sarthak1357 → CSES shortest routes 1
Palestinian_Dream → Extracting Mathematical Ideas Behind The Problems
Beacon → Video solutions to IOI problems
I_HATE_CONSTRUCTIVES. → IZhO 2024 day 1 discussion
mohammed_orkhan → I wnat to be EXPERT!!
SAD_IN_NIGHTMARE → 2024 OIs
usaxena95 → SOS Dynamic Programming [Tutorial]
maomao90 → Editorial for Hello 2024
MohammadParsaElahimanesh → Codeforces Global Round 23 Editorial
MikeMirzayanov → Codeforces Single Account Policy: zh0ukangyang is Removed from the Rating
cloud_eve → Elementary Number Theory
nor → [Tutorial] An elementary way of solving recurrences
flamestorm → Codeforces Round 918 (Div. 4) Editorial
ATSTNG → Does Polygon automaticly send statements and tutorials of all problems into AI service?
Sammarize → Codeforces Beta Round 79, разбор задач
Victor_Luis123 → Is Dijkstra’s overrated.
Aakas_kumar → All Pair of sum
molney → Разбор Codeforces Round 909 (Div. 3)
maomao90 → I am top 1 contributor. AMA!
Vladosiya → Codeforces Round 913 (Div. 3) Editorial
Максимальная глубина рекурсии в Python и как её увеличить
Рекурсия — это техника в программировании, при которой функция вызывает саму себя напрямую или косвенно. Она может быть очень полезной для решения определенных задач, но имеет свои ограничения. Одно из них — максимальная глубина рекурсии.
В Python предусмотрено ограничение на максимальную глубину рекурсии, чтобы предотвратить переполнение стека и последующий сбой программы. Это ограничение обычно установлено на достаточно высоком уровне (обычно порядка 1000), но иногда, для решения определенных задач, может потребоваться увеличить этот лимит.
def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) print(factorial(2000))
В этом коде функция factorial рекурсивно вызывает сама себя для вычисления факториала числа. Но при попытке вычислить факториал числа больше 1000, получаем ошибку RecursionError: maximum recursion depth exceeded in comparison .
Чтобы увеличить максимальную глубину рекурсии, можно использовать функцию sys.setrecursionlimit(limit) . Эта функция устанавливает максимальную глубину рекурсии на указанное значение. Но стоит быть осторожным, увеличивая этот лимит, так как это может привести к переполнению стека и сбою программы.
import sys sys.setrecursionlimit(3000) print(factorial(2000)) # Теперь это работает
Таким образом, хотя увеличение максимальной глубины рекурсии может быть полезным, с ним следует обращаться с осторожностью. Более того, часто большие глубины рекурсии указывают на то, что задача, возможно, может быть решена более эффективным способом, не используя рекурсию.
Python-сообщество
![[RSS Feed]](http://python.su/static/djangobb_forum/img/feed-icon-small.png){kind=icon}
- Начало
- » Python для новичков
- » Проблемы с рекурсией
#1 Окт. 14, 2010 18:58:31
Андрей Светлов От: Зарегистрирован: 2007-05-15 Сообщения: 3137 Репутация: 14 Профиль Адрес электронной почты
Проблемы с рекурсией
Сейчас будет много теории — а потом варианты решения.
Стек — непрерывная область памяти (в виртуальной адресации, разумеется).
Резервируется окно и в нем сверху выделяется кусок памяти.
По умолчанию на винде это выглядит так: ]
Размер стека потока должен быть указан до запуска этого самого потока, естественно.
Также очевидно, что готовый стек уже нельзя перенести в другое место — в нем записаны абсолютные адреса, перенос все ломает.
В общем случае стек еще и нельзя расширить — место за границами окна может быть занято.
Т.е. стек — это навсегда, пока поток не помрет.
Почему нельзя резервировать сразу очень много? Да потому, что объем виртуальной (адресуемой) памяти — конечен.
На Windows 32 bit это 2 гигабайта. Каждый поток ест по крайней мере 2 мегабайта на свой стек. Результат — невозможно запустить больше тысячи потоков.
На практике это число еще меньше.
Далее. Максимальный размер стека можно указать перед запуском потока — есть такой параметр у CreateThread.
Но для нового процесса размер стека для главного потока указать нельзя — CreateProcess о таком не заботится.
В linux есть ulimit, в Windows — ничего. А после запуска процесса (нашего питона, например) уже ничего поменять нельзя — поток стартовал, поезд ушел.
Но способ регулировки есть. В заголовках образа (exe файла, если по простому) есть параметр, указывающий размер зарезервированного стека.
Запускаем cmd.exe
cd “C:\Program Files\Microsoft Visual Studio 9.0\VC\”
vcvarsall.bat
cd bin
dumpbin.exe /HEADERS c:\Python27\python.exe
Выводит длинную простыню. Во втором заголовке (OPTIONAL HEADER VALUES) находим 1E8480 size of stack reserve. Это наши 2 мегабайта.
Увеличим вдвое:
editbin.exe /STACK:4000000 c:\Python27\python.exe
Через dumpbin можно проверить результат.
Выглядит кривовато — да так оно и есть. Не трогая питон — стек не увеличишь.
Есть еще один вариант. Сделать свой exe — запускатель интерпретатора (это несложно) и в нем указать желаемый размер стека.
Или запаковать все py2exe — а дальше вы поняли. Можно и py2exe поправить, чтобы размер сразу нужный был.
Главный вывод — не трогая запускаемый файл — стек не увеличишь (для главного потока).
Для потоков, созданных из питона можно перед запуском потока вызвать threading.stack_size
Только помните — размеры стеков станут разными. А это тоже неудобно и выглядит опять таки хаком.