Переполнение стека в рекурсии Python - PullRequest
Новая
       21

Переполнение стека в рекурсии Python

1 голос
/ 18 марта 2019

Я делаю задачу Эйлера проекта 78

Пусть p(n) представляет количество различных способов, которыми n монеты могут быть разделены на стопки. Например, пять монет можно разделить на стопки ровно семью различными способами, поэтому p(5)=7

Найдите наименьшее значение n, для которого p(n) делится на миллион.

Я пытаюсь решить эту проблему с помощью рекурсии. Я знаю, что это не оптимальное и не самое быстрое решение, но я хочу сделать эту работу, если это возможно. Около n = 6000 это дает мне:

MemoryError: переполнение стека

И это не единственная проблема. Я проверил онлайн, и решение составляет около 53 000. Моя матрица идет только до 10 000x10 000. Если я перейду к 60,000x60,000, он вернет MemoryError. Вот мой код: 

import sys
from time import process_time as timeit

sys.setrecursionlimit(100000)

table = [10000 * [0] for i in range(10000)]

def partition(sum, largestNumber):
    if (largestNumber == 0):
        return 0

    if (sum == 0):
        return 1

    if (sum < 0):
        return 0

    if (table[sum][largestNumber] != 0):
        return table[sum][largestNumber]

    table[sum][largestNumber] = partition(sum,largestNumber-1) + partition(sum-largestNumber,largestNumber)
    return table[sum][largestNumber]



def main():
    result = 0
    sum = 0
    largestNumber = 0
    while (result == 0 or result%100000 != 0):
        sum += 1
        largestNumber += 1
        result = int(partition(sum,largestNumber))
        if sum%1000 == 0:
            print('{} {}'.format(sum,timeit()))

    print("n = {}, resultado = {}".format(sum,result))
    print('Tempo = {}'.format(timeit()))
if __name__ == '__main__':
    main()
...