8

私はこの質問で言及されたアルゴリズムが好きです：「これはどのように機能しますか？ハノイの塔ソリューションの奇妙な塔」 これはどのように機能しますか？ハノイの塔ソリューションの奇妙な塔

ハノイの塔の非再帰的なソリューションをスケーリングして、XディスクとYタワーを使用し、タワーをスタックとして表す方法はありますか？

4

1 に答える 1

1

Y=3 タワーと X ディスクを使用したハノイのタワーの反復解は、ウィキペディアで見つけることができます。

偶数のディスクの場合:

  • ペグAとBの間で正当な動きをする
  • ペグAとCの間で正当な動きをする
  • ペグ B と C の間の正当な動きを完了するまで繰り返します

奇数のディスクの場合:

  • ペグAとCの間で正当な動きをする
  • ペグAとBの間で正当な動きをする
  • ペグ B と C の間の正当な動きを完了するまで繰り返します

いずれの場合も、合計 2^X-1 回の移動が行われます。このアルゴリズムでの移動数は、 Y=3 の場合のみ最小になります。

このソリューションは他のタワーを無視するため、任意の Y >= 3 および任意の X で機能します。

3 つのペグのバージョンには、上で概説したように単純な再帰的な解法がありますが、4 つのペグを使用したハノイの塔問題 (レーブのパズルと呼ばれます) の最適解は、さらに多くのペグは言うまでもなく、まだ未解決の問題です。これは、問題の制約の 1 つを少し緩めることによって、単純で解決可能な問題を劇的に難しくする方法の良い例です。

ウィキペディアより引用。

于 2011-02-20T11:51:28.840 に答える