0

私はプログラミングが初めてで、基本的な Python を使用して Project Euler で この問題を解決しようとしていました。

基本的に、各段階で選択された最大値に基づいて再帰を使用し、リストを使用して将来の選択のために可能なオプションを維持しようとしました。

コードは短く、以下に示します。

def func(n,l):
    if n<0:
        return 0
    if l==[1] or n==0:
        return 1
    else:
        j=0
        while l != []:
            j=j+func(n-l[0],l) 
            del l[0]
        return j

print func(200,[200,100,50,20,10,5,2,1])

たとえば、 

func(5,[5,2,1])

再帰はそれをに分割します

func(0,[5,2,1]) + func(3,[2,1]) + func(4,[1])

しかし、コードは決して通らないようです。エラーがlist-index-out-of-range発生したか、maximum-recursion-depthエラーが発生したと表示されます (非常に小さなおもちゃのインスタンスの場合でも)。私は間違いを見つけることができません。どんな助けでも大歓迎です。

4

3 に答える 3

3

Python では、リストは参照によって関数に渡されますが、値によって渡されることはありません。プログラムの最も簡単な修正は、再帰呼び出しを に変更することfunc(n - l[0], l[:])です。このようにして、リストは値渡しされます。

于 2013-03-28T08:09:57.920 に答える
1

あなたが考慮に入れていないことの1つは、次のことです。

j=j+func(n-l[0],l)

のコピーを作成しませんl。

したがって、すべての再帰呼び出しはfunc同じリストで動作します。最も内側の呼び出しが and の最後の要素を削除してl戻ると、その呼び出し元は . を試みてdel l[0]取得しIndexErrorます。

于 2013-03-28T08:07:25.893 に答える
1

各再帰で、次の 2 つの決定を行います。

  1. f利用可能なコインの種類から最初のコインを取り (例えば これにより、サブ問題 func(n - f, l) が発生します
  2. 最初のコイン タイプは無視して、残りのコイン タイプから n を作成できるかどうかを確認します。これにより、サブ問題 func(n, l[1:]) が発生します

組み合わせの総数は、2 つのサブ問題の合計になります。したがって、コードは次のようになります。

def func(n, l):
    if n == 0:
        return 1
    if n < 0 or len(l) == 0:
        return 0
    if l == [1] or n == 0:
        return 1

    return func(n - l[0], l) + func(n, l[1:])

のコピーの各再帰lは によって作成されl[1:]ます。これは、次の再帰の前の要素で省略できpop、その後で復元できますappend。

def func(n, l):
    if n == 0:
        return 1
    if n < 0 or len(l) == 0:
        return 0
    if l == [1] or n == 0:
        return 1

    full = func(n - l[-1], l)
    last = l.pop()
    partial = func(n, l)
    l.append(last)
    return full + partial
于 2013-03-28T08:27:28.740 に答える