2

注: 再帰的な解決策を理解しています。しかし、コードの実行の段階をたどることができないため、コードがどのようにそれを達成しているかわかりません。

ハノイの塔の再帰ループを理解するのに苦労しています。手順がどのように動作しているかを確認するためにさまざまな戦術をコメントして試してみましたが、ループがどのように動作しているか、リングがどのように向けられているかを把握できないようです.

  def move(rings, from, destination, other)
    if rings == 1
      ring = from.pop
      p "Move ring #{ring} from #{from} to #{destination}"
      destination.push ring
    else
      move(rings-1, from, other, destination)
      move(1, from, destination, other)
      move(rings-1, other, destination, from)
    end
  end

出力は次のとおりです。

"Move ring 1 from a to c"
"Move ring 2 from a to b"
"Move ring 1 from c to b"
"Move ring 3 from a to c"
"Move ring 1 from b to a"
"Move ring 2 from b to c"
"Move ring 1 from a to c"

さまざまな説明を見てきましたが、ループがどのように実行されているかを説明しているものはありません。たとえば、上記のように、リングが偶数の場合、最初のステップでリング 1 が a から b に配置されるのに対し、すべての奇数のリングでは a から c に配置される理由がわかりません。

ソリューションの背後にあるロジックを理解しています。補助ペグを使用しているときに n 個のリングを目的地に移動するには、最初に n-1 個のリングを補助ペグに移動し、次に n 番目のリングを目的地に移動して繰り返す必要があります。最初の手順をもう一度。しかし、配置の方向がどのように変化しているかはわかりません。たとえば、上記の move メソッドの呼び出しが c から b に言及していないように見える場合、ブロックが c から b に移動する方法がわかりません。

お時間を割いてご協力いただき、ありがとうございました。

また、Ruby でコード実行のプロセスを追跡するのに役立つ提案があれば、お知らせください。物事がどのように実行されているかわからないインスタンスをトラブルシューティングする方法について、あなたの洞察を聞きたいです。

あなたの答えを聞きたいです:)

4

1 に答える 1

6

ハノイの塔は、分割統治法アルゴリズムの優れた例です。最後の要素を除くすべての要素をスペアに移動し、最後の要素をソースから宛先に移動することで、ソースから宛先にすべてを移動できると考えるアルゴリズムがあるため、すべてをスペアから宛先に移動します。

基本ケースではない move のすべての呼び出しは、基本ケースに到達するまで指数関数的にさらに 2 つの呼び出しに分割されます。最初の部分 (中央の要素を移動する前) のみを考慮した 3 ディスク ゲームのトレースは次のとおりです。

move(3, source, dest, spare)
move(2, source, spare, dest)
move(1, source, dest, spare)

「ソースからスペアへのリング1の移動」を出力する場所

ここでのコツは、渡される引数 (スタック) がレベルごとに異なる役割を持つことです。2. レベルの場合、宛先は 3. レベル スペアです。スペアから宛先に突然移動すると、ソースがスペアとして使用されますが、関数はそれを気にしません。ベースケースに当たるまでシャッフルするだけです。n 個のディスクに対して 2^n-1 回の移動 (ベース ケース ヒット) があります。

再帰は戻る前に 2 番目のレベルを終了し、3. レイヤーは別の 2. レイヤーを開始します。移動後、スペアから目的地に移動します。

ヒント: 先頭に「entering 3, a, c, b」、最後に「exiting 3, a, c, b」などのトレース テキストを追加する必要があります。これにより、再帰が何回行われ、どのように行われたかがよくわかります。

于 2013-08-21T22:26:41.913 に答える