3

kアイテムのセットからアイテムを選択する方法の数を計算するための再帰的な式はn、 で示さC(n,k)れます。

           1                    if K = 0
C(n,k) = { 0                    if n<k
           c(n-1,k-1)+c(n-1,k)  otherwise

この再帰式を使用しCて計算する再帰関数を作成しようとしています。C(n,k)私が書いたコードは自分の思い通りに動くはずですが、正しい答えが得られません。

これは私のコードです：

def combinations(n,k):
    # base case
    if k ==0:
        return 1
    elif n<k:
        return 0
    # recursive case
    else:
        return combinations(n-1,k-1)+ combinations(n-1,k)

答えは次のようになります。

>>> c(2, 1)
0
>>> c(1, 2)
2
>>> c(2, 5)
10

しかし、私は他の数字を取得しています...コードのどこに問題があるのか​​ わかりません。

4

3 に答える 3

6

書かれているように、引数を逆にしてみn < kます。

私はあなたがこれを意味すると思います：

>>> c(2, 1)
2
>>> c(5, 2)
10
于 2013-05-29T20:03:53.963 に答える
5

あなたの呼び出しは、例えば、それをc(2, 5)意味します（質問の上部にある c の定義に従って）。そのため、結果は. そして、それはまさにあなたの実装で起こることです。また、他のすべての例でも実際に正しい結果が得られます。n=2k=5n < k0

サンプル テスト ケースの引数の順序が正しいことは確かですか? それらはすべてc(k, n)呼び出しであるためです。したがって、これらの呼び出しが間違っているか、定義の順序cがオフになっています。

于 2013-05-29T20:13:01.567 に答える
4

これは、再帰関数を実際に使用してはならない場合の 1 つです。組み合わせの計算は、直接行うのは非常に簡単です。階乗関数のように、末尾再帰で最適化できるため、再帰を使用しても大したことはありません。

理由は次のとおりです。

プログラムを書くときに、フィボナッチ数列にこの定義を使用しないのはなぜですか?

def fibbonacci(idx):
    if(idx < 2):
        return idx
    else:
        return fibbonacci(idx-1) + fibbonacci(idx-2)

その理由は、再帰のために法外に遅いからです。同じ理由で、可能であれば複数回の個別の再帰呼び出しは避けるべきです。

どうしても再帰を使用したい場合は、最初にこのページを読むことをお勧めします。より優れた再帰実装では、毎回 1 回の再帰呼び出しのみが必要になります。 Rosetta コードには、かなり優れた再帰実装もいくつかあるようです。

于 2013-05-29T20:24:58.203 に答える