0

我最近问了这个问题并得到了第一个答案。我正在尝试将其放入 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)

我的代码有什么问题？我需要改变什么？我不知道怎么了。请帮忙。谢谢！

4

2 回答 2

7

你的代码太复杂了。你可以写一个几乎一对一的转录你在数学交流中得到的答案：

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

通过这两种实现，我得到 12660 作为f(10, 12, 70).

于 2013-02-19T11:39:59.173 回答
0

我不知道为什么你的不起作用，但这里有一个实现，IMO 更具可读性：

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是惊人的。

于 2013-02-19T11:46:08.830 回答