如何在Python中编写递归sigma的递归公式？

Question

我最近在这个地方问了一个问题，并得到了第一个答案。我正在尝试把这个问题用Python代码实现。这是我写的代码，但我总是得到0作为结果。

def f(n, k, s):
    ans = 0
    for j in range(1, min({k,s}) + 1):
        print j
        if (n == 1):
            if (k >= s):
                ans = ans + 1
            elif (k < s):
                ans = ans + 0
            elif (s > n):
                ans = ans + 0
        elif (n*k < s):
            ans = ans + 0
        else:
            ans = ans + f(n-1,j,s-j)
    return ans

print f(10, 12, 70)

我的代码哪里出问题了？我需要改什么？我不知道哪里错了。请帮帮我。谢谢！

Answer 1

我不知道你那段代码为什么不行，但这里有一个可以用的实现方式，我觉得这个写起来清晰多了：

from itertools import permutations


def f(n, k, s):

    if k > s:
        k = s-1

    count = 0
    sum_perms = []

    number_list = []
    for i in range(1,k):
        for j in range(1,k,i):
            number_list.append(i)

    for perm in permutations(number_list, n):
        if sum(perm) == s and perm not in sum_perms:
            sum_perms.append(perm[:])
            count += 1

    return sum_perms, count

不过，这种方法比递归的方式要慢很多 :-(

itertools 真是太棒了。

Answer 2

你的代码太复杂了。其实你可以几乎直接把在数学交流网站上得到的答案写出来：

def f(n, k, s):
    if n == 1:
        return int(k >= s)
        # or: 1 if k >=s else 0 
    return sum(f(n-1, j, s-j) for j in range(1, min(k, s)+1))
    # to make it faster:
    #return sum(f(n-1, j, s-j) for j in range(1, min(k, s)+1) if n*k >= s)

你代码中的问题是，你把基础情况的检查放在了循环里面，其实应该放在外面：

def f(n, k, s):
    ans = 0
    if n == 1:
        return int(k >= s)

    for j in range(1, min({k,s}) + 1):
        print j
        if n*k >= s:
            ans += f(n-1,j,s-j)
    return ans

用这两种实现方式，我在计算 f(10, 12, 70) 时都得到了12660这个结果。