整数の整数分割数を計算する再帰プログラムに問題があります。
ここに私が書いたものがあります:
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
ウィキペディアの再帰とアルゴリズムの両方を正しく実装したと思っていたので、なぜ私のプログラムが適切に動作しないのかわかりません。誰かがそれが何をしているのか理解するのを手伝ってくれますか?