13

これは、引数 n と k を持つサブセット問題のコードです。n は学生の総数を表し、k は n から取得したい学生の数を表します。このコードは、n 人の学生から k 人の学生を引き出すことの可能な組み合わせの数を与えようとします。

def subset(n, k): 
    if k == 0:
        return 1
    if n == k:
        return 1
    else:
        return subset(n-1, k-1) + subset(n-1, k)

再帰呼び出しの最初の部分は理解できますが、+ サブセット(n-1, k) の部分が理解できません。誰かが私にこれを説明できますか?

4

3 に答える 3

32

再帰は単純な観察に基づいており、式による数学的証明ではなく、なぜそれが真であるかについて組み合わせ論的議論を行います。

kから要素を選択する場合は常にn、次の 2 つのケースがあります。

  1. 要素を選択します#n
  2. 要素を選ばない#n

#nこれらのイベントは相互に排他的であるため、組み合わせの合計数は、 を選択した場合の組み合わせの数と、選択しなかった場合の組み合わせの数によって与えられます#n。

エレメントの選択#n

すでに 1 つの要素を選択しているので、別の要素を選択するだけで済みますk-1。また、含まれるか含まれないかについては、すでに 1 つの要素が決まっているので、残りのn-1要素のみを考慮する必要があります。

したがって、要素を選択するための組み合わせの量は#n、

    subset(n - 1, k - 1)

要素を選ばない#n

選択する要素はまだありkますが、 element については既に決めているので、選択する要素#nだけが残りn - 1ます。したがって：

    subset(n - 1, k)

ベースケース

n再帰は、通常、要素が解の一部である解とそうでない解の 2 つの状況を区別できるという事実を使用します。

ただし、そのような区別は常にできるとは限りません。

  • すべての要素を選択する場合 (n == k以下のコードのケースに対応)
  • または要素をまったく選択しない場合 (k == 0以下のコードのケースに対応)

これらの場合、解は厳密に 1 つしかないため、

if k == 0:
    return 1
if n == k:
    return 1

確実に機能するようにする

そのためには、基本ケースが常にある時点でヒットすることを自分自身に納得させる (または証明する) 必要があります。

n < kある時点でそれを仮定しましょう。私たちの仮定によれば、nはもともと より大きいか等しいので、 とが一斉に減少するか、1 だけ減少するため、ある時点がkあったに違いありません。n = knkn

これは、subset(n - 1, k)それが起こるために への呼び出しがあったに違いないことを意味し、それは より下にn減少しますk。n = kただし、定数を返す場所には基本ケースがあるため、これは不可能1です。

nある時点で のように減少するか、または の正確な回数n = kで一斉に減少すると結論付けます。kk = 0

したがって、基本ケースは機能します。

于 2012-10-20T11:19:21.937 に答える
1

これは数学的な問題であり、プログラミングの問題ではありません。あなたがしているのは、二項係数を計算することです。式は次のとおりです。

(n, k) = (n-1, k-1) + (n-1, k) with all (n, 0) and (n, n) having a value of 1.

完全な説明については、こちらを参照してください。再帰的な解決策は、ここで見ることができます。上記のリンクが無効になった場合は、Google を使用して検索してください。ウィキペディアでこの記事を読んだ後よりも、SO に関するより良い説明が得られるとは思えません。

于 2012-10-19T09:18:31.133 に答える