5

現在、ダグラス・クロックフォードの本を読んでいますが、ハノイの塔の機能は少し頭に浮かびます。コンソールにログを記録しても、何が起こっているのか本当に理解できませんでした。これが私の追加機能です：

var hanoi = function (disc, src, aux, dst) {
  console.log(disc);
  console.log(src, dst);    
  if (disc > 0) {
    hanoi(disc - 1, src, dst, aux);
    console.log('Move disc ' + disc + ' from ' + src + ' to ' + dst);
    hanoi(disc - 1, aux, src, dst);
  }
}

hanoi(3, 'Src', 'Aux', 'Dst');

これにより、次のようになります。

3
Src Dst
2 Src
Aux
1
Src Dst 0SrcAux ディスク
1 をSrcから Dstに移動 0AuxDst ディスク2をSrcからAuxに移動 1DstAux 0DstSrc ディスク 1 をDstから Auxに移動 0SrcAux ディスク3をSrcから移動to Dst 2 Aux Dst 1 Aux Src 0AuxDst ディスク1をAuxから Srcに移動 0DstSrc ディスク2をAuxからDstに 移動 1SrcDst 0SrcAux ディスク 1 をSrcからDstに移動




























0
Aux Dst

そして、私は早い段階で迷子になっています。結果の6行目で、SrcAuxからSrcDstに戻るにはどうすればよいですか？

そして、関数が「disc-1」を使用して自分自身を呼び出しているだけのときに、ディスクの数が0に達した後、どのようにしてディスクの数を増やすことができますか？

4

2 に答える 2

9

出力のテキスト表現が再帰を理解するための最良の方法ではないため、混乱が生じます。ディスクの数は「増えている」のではなく、hanoi(1)一度実行されると実行を継続しますhanoi(0)。

JSBinで、スペースを使用して（やや）きれいな方法で出力を出力する変更された例を作成しました。「moves」だけが実際に何かを実行します。残りの行は、後で問題全体に取り組むために、より小さなサブ問題を解決するための再帰呼び出しです。

また、アルゴリズムがどのように機能するかをグラフィカルに示すこのJavaアプレットも確認​​することをお勧めします。これは理解しやすいかもしれません。

于 2010-09-18T16:10:22.540 に答える
5

ハノイの塔は、再帰によって特定の問題を単純化する方法の優れた例です。考え方は次のとおりです。N個のディスクをソーススタックから宛先スタックに一度に1つずつ移動する必要があり、小さいディスクに大きいディスクを配置することはできません。補助スタックを使用できます。N=10としましょう。それを解決する方法がわかりません。しかし、あなたは問題をより単純にすることができます（あなたが望む）： 

move 9 disks to the auxiliary stack,  
move the remaining (and largest!) disk to the destination stack, and  
move the 9 disks from the auxiliary stack to the destination stack

繰り返しますが、9ディスクスタックを移動する方法がわかりませんが、それも問題ありません。 

move 8 disks from the auxiliary stack to the source stack,  
move the remaining disk to the destination stack (there are 2 disks now), and  
move the 8 disks from the source stack to the destination stack

移動する必要のあるスタックが1ディスクだけになるまで、これを繰り返します。

再び増加するディスクの数について：関数内でNに割り当てられているN-1ディスクに対して関数を再帰的に呼び出します。このNは、関数が終了するまでのみ存在し、前のレベルに戻ります。次に、Nの古い値を再度取得します。

于 2010-09-18T16:11:51.087 に答える