python - 整数分区的递归公式

我编写了以下代码，使用涉及五边形数字的递归公式评估整数分区：

def part(n):
    p = 0
    if n == 0:
        p += 1
    else:
        k = 1
        while ((n >= (k*(3*k-1)/2)) or (n >= (k*(3*k+1)/2))):
            i = (k * (3*k-1)/2)
            j = (k * (3*k+1)/2)
            if ((n-i) >= 0):
                p -= ((-1)**k) * part(n-i)
            if ((n-j) >= 0):
                p -= ((-1)**k) * part(n-j)
            k += 1
    return p

    n = int(raw_input("Enter a number: "))
    m = part(n)
    print m

该代码可以正常工作直到n=29。在n=24周围它变慢了一点，但是我仍然在不错的运行时中得到了输出。我知道该算法是正确的，因为得出的数字与已知值一致。

对于35以上的数字，即使等待了很长时间（大约30分钟），我也没有输出。我的印象是python可以处理比此处使用的数字大得多的数字。有人可以帮助我改善运行时间并获得更好的结果吗？另外，如果代码有问题，请告诉我。

最佳答案

您可以使用Memoization：

def memo(f):
    mem = {}
    def wrap(x):
        if x not in mem:
            mem[x] = f(x)
        return mem[x]
    return wrap

@memo
def part(n):
    p = 0
    if n == 0:
        p += 1
    else:
        k = 1
        while (n >= (k * (3 * k - 1) // 2)) or (n >= (k * (3 * k + 1) // 2)):
            i = (k * (3 * k - 1) // 2)
            j = (k * (3 * k + 1) // 2)
            if (n - i) >= 0:
                p -= ((-1) ** k) * part(n - i)
            if (n - j) >= 0:
                p -= ((-1) ** k) * part(n - j)
            k += 1
    return p

演示：

In [9]: part(10)
Out[9]: 42

In [10]: part(20)
Out[10]: 627

In [11]: part(29)
Out[11]: 4565

In [12]: part(100)
Out[12]: 190569292

有了备忘录，我们会记住之前的计算，因此对于重复的计算，我们只需要在字典中进行查找即可。

关于python - 整数分区的递归公式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34421813/