python - Python 中递归整数分区计算器的未知问题

Question

我的递归程序在计算整数的整数分区数时遇到了一些问题。

这是我写的:

def p(k, n):
    if k > n:
        return 0
    if k == 1:
        return 1
    else:
        return (p(k+1, n) + p(k, n-k))

def partitions(n):
    ans = 1
    for k in range(1, n/2):
        ans += p(k, n-k)
    return ans

这个算法是从维基百科的文章Partition (number theory)实现的.这是我的程序对前几个整数的输出:

partitions(0) = 1
partitions(1) = 1
partitions(2) = 1
partitions(3) = 1
partitions(4) = 2
partitions(5) = 2
partitions(6) = 2
partitions(7) = 2

我不确定为什么我的程序不能正常运行，因为我认为我正确地实现了维基百科的递归和算法。有人可以帮助我了解它在做什么吗？

Answer 1

我看到两个问题:

这个:

if k == 1:

应该是if k == n:，并且这个循环:

for k in range(1, n/2):

应该是 range(1, n/2+1) —— 或者更好，range(1, n//2+1) 来明确事实上我们想要整数除法——因为 Python 中的 range 不包括上限。修复这些后，我得到:

>>> [partitions(i) for i in range(1,10)]
[1, 2, 3, 5, 7, 11, 15, 22, 30]

(您会注意到，它只有 9 个值。:^)