2

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

这是我写的：

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

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

4

2 回答 2

2

您的基本情况之一是错误的：

if k == 1:
    return 1

应该

if k == n:
    return 1

此外：

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

应该

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

这是因为公式中的总和包含上限，但在 Python 中，range不包含上限。然后：

print [partitions(i) for i in range(1, 8)]

给

[1, 2, 3, 5, 7, 11, 15]

匹配维基百科文章中给出的值。

于 2013-07-23T03:16:47.820 回答
2

我看到两个问题：

这个：

if k == 1:

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

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

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

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

（你会注意到，它只有 9 个值。:^）

于 2013-07-23T03:17:30.197 回答