0

前もってお詫び申し上げます。この質問は、私が望む/必要な結果をもたらさない回答で以前に尋ねられたことを認識しています. Python3で次のことを行う関数を作成しようとしています:

指定された金額を生成するすべての方法 (コインの組み合わせ) を返す再帰関数が必要です。この関数には、金額とコインの 2 つの引数のみを含めることができます。再帰について頭を悩ますのに苦労したので、説明も大歓迎です。ありがとう。

これが私が現在持っているものです：

COINS = dict(
    USA=[100, 50, 25, 10, 5, 1],
    AUSTRALIA=[200, 100, 50, 20, 10, 5],
    UK=[500, 200, 100, 50, 20, 10, 5, 2, 1]
)

def change(amount, coins):
    """
    >>> change(100, COINS['USA'])
    293
    """
    if amount < 0:
        return 0
    elif amount == 0:
        return 1
    else:
        biggestcoin, *rest = coins[0], coins[1:]
        return change(amount-biggestcoin, coins) + change(amount, rest)
4

2 に答える 2

3 
biggestcoin, *rest = coins[0], coins[1:]

両側に 2 つのアイテムがあるためrest、論理的には ではなく、ここが必要です。*restここで使用*restすると、リスト ラッピングの追加レイヤーが作成され、おそらく発生している例外が発生します。

それを修正したら、各コイン 1 枚で希望の金額を作れなかったらどうなるか考えてみてください。change(amount, rest)再帰呼び出しは最終的にamountゼロより大きく、rest空の状態で発生します。その場合も処理する必要があります。

于 2012-03-22T01:17:08.833 に答える
1

再帰の背後にある考え方は単純です。

少しずつ、問題のサイズを小さくしてみてください。

それができれば、ほぼ完了です。大きな問題から始めて、非常に小さな問題になるまで、少しずつサイズを小さくしていきます。好きなように解決できます。

これは、変更を行う問題にどのように適用されますか? そうですね、作れnと言われたら、コイン1枚で問題が少し減りますね。そして続けていくと、最終的には十分に小さな問題を解決できるようになります!

于 2012-03-22T01:17:35.927 に答える