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

コードが複雑すぎます。あなたは数学の交換で得た答えのほぼ1対1の転写を書くことができます：

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 に答える