ハノイの塔タスクは、主に再帰的ソリューションの概念を説明するために、初心者プログラマーに提供される最初のタスクの1つです。 この記事では、再帰なしで理論的に現在の動きに最適なソリューションを示すことができる方法を提供します。
ハノイの塔は、19世紀の人気のパズルの1つです。 3つのロッドが与えられ、そのうちの1つに8つのリングが張られており、リングはサイズが異なり、大きいほど小さくなります。 課題は、最小限の動きで8つのリングのピラミッドを別のロッドに移動することです。 一度に転送できるのは1つのリングのみであり、小さいリングに大きいリングを配置することはできません。
3本のロッドを使用したこの問題の古典的な解決策は、与えられた数のリングnに対して、シフトの数が次の式で計算されることを示唆しています。
。
このタスクのさらなる魅力は、それに付随する凡例によって与えられます。
世界の真ん中にある大聖堂の下にあるベナレスの大寺院には、3本のダイヤモンドロッドが固定されたブロンズディスクがあり、1本の肘は高さ、ハチの厚さです。 むかしむかし、この修道院の僧ksたちは、ブラフマ神の前で罪を犯していました。 怒り狂ったブラフマーは、3本の高い棒を立て、そのうちの1本に純金で作られた64個のディスクを置きました。 さらに、小さなディスクが大きなディスク上にあるようにします。 64個すべてのディスクが、ブラフマが世界の創造中に置いた棒から別の棒に移されるとすぐに、塔と神殿は塵に変わり、世界は雷の下で死にます。
その間に、新人は、このソリューションの複雑さを評価して結果に感動するよう招待されます。僧ksが作成しなければならないディスクの数は18,446,744,073,709,551,615です。 昼も夜も働いている僧ksが1秒ごとにディスクを1回動かすと、彼らの仕事は5840億年続きます。
ソリューションの本質は、現在のディスクを移動するために、以前のすべてのディスクを空きコアに転送し、必要なディスクを移動してから、以前のすべての小さいディスクを必要なコアに戻す問題を解決する必要があることを理解することです。 したがって、問題の解決策は以前の解決策に還元され、再帰メカニズムを示しています。
Alexander Busarov MrShoorは、非常に有益な投稿を書いて、対応するWikipediaの記事を完全に補完し、非常に詳細なプログラムコードで、再帰の実装に慣れることをお勧めします。
同じ投稿には、アルゴリズムのフラクタル性の説明があります。 この特定のタスクへのグレイコードの適用を明らかにしながら、この方向を続けようとします。
対応するウィキペディアの記事から引用します。
ハノイの塔の問題を解決するためにグレーコードが使用されます。 Nをディスクの数とします。 ゼロのみで構成される長さNのグレイコード（つまり、G（0））から始め、グレイコードに沿って移動します（G（i）からG（i + 1）に進みます）。 現在のグレイコードの各I番目のビットをI番目のディスクに関連付けます（最小のディスクは最小のビットに対応し、最大のビットは最も古いビットに対応します）。 各ステップで正確に1ビット変化するため、ビットIの変化は最初のディスクの動きとして理解できます。 最も小さいディスクを除くすべてのディスクについて、各ステップに移動オプションが1つだけあることに注意してください（開始位置と最終位置を除く）。 最小のディスクの場合、移動には常に2つのオプションがありますが、常に答えにつながる移動を選択するための戦略があります。Nが奇数の場合、最小のディスクの移動シーケンスはf-> t-> r-> f-> t-> r-> ... （fは開始ロッド、tは最終ロッド、rは残りのロッドです）、Nが偶数の場合、f-> r-> t-> f-> r-> t-> ...
問題の最適な解決策は、次の移動後にディスクの位置を決定することです。 最初（ゼロストローク）で、すべてのディスクは同じ開始ロッドf上にあります。 ディスクウェイトの番号付けは、番号1から昇順に実行されます。 コース内のディスクの位置を数字mで記述する必要があります。
明らかに、移動後の最適な解決策mでは、ディスクの数nは
（1） 。
残りの大きなディスクは無視できます。これは、初期の3ロッド問題でディスクの数が無限であるというより一般的な仮定の下では非常に便利です。
次に、移動するディスクの数を決定したら、それらの位置を決定します。
上記のソースに記載されているソリューションのフラクタル性により、ソリューションの相互の「ネスト」により、移動番号のバイナリコードと移動されたディスクの番号の関係が明らかになることが明らかになります。
特に、この移動中に、「移動」のi が現在の移動の数mから1を引いたバイナリ展開の2の最大出力と相関するディスク移動が行われます。
（2） 。
MrShoorが彼のコードで使用するのと同じPascal / Delphi表記では、これは次のように記述できます。
i:=0; deg2value:=1; while ((m mod deg2value) = 0) do begin i:=i+1; deg2value:=deg2value*2; end;
したがって、重みiの各ディスクについて、指定された重みのディスクが最後に移動した移動jを判別できます。
。
重みi を使用した最後のディスク移動のnum_move移動番号を決定するためのコードは、似ているように見える場合があります（Mathモジュールが有効になっている場合）。
deg2value:=Power(2,i-1); q_move:=m div deg2value; if (q_move mod 2) = 0 then q_move:=q_move-1; num_move:=q_move * deg2value; q_move=(q_move+1) div 2;
q_move変数の途中で、ゲームの開始から重みiのディスク移動の数が取得されるという事実に注意する価値があります。
そのため、暫定的に、各移動後にゲーム中に各ディスクが何回移動されたかがわかります。 次に、各ディスクの移動先を決定します。
ウィキペディアで述べたように、上部ディスクの動きは周期的であり、特定の宛先ロッドtを選択するときにNが奇数の場合、最小ディスクの動きのシーケンスはf-> t-> r-> f-> t-> r-> ...（ここでf-starting rod、t-final rod、r-remaining rod）、およびNが偶数の場合、f-> r-> t-> f-> r-> t-> ...
フラクタリティを思い出すと、前のディスクの上部を破棄すると、現在のディスクも同様に周期的に動きます。 この事実を考えると、ディスク番号のパリティに応じて、奇数ディスクを移動するサイクルは最初のディスクを移動するサイクルと一致し、偶数ディスクを移動するサイクルはロッドtとrの順序で異なることが明らかになります。
特に、q_moveの移動数と現在のディスク番号のパリティがわかっているので、残りを単純に3で除算して、ディスクが移動した最後のピンを決定できます。
したがって、入力にディスクの総数N、選択された宛先ロッドt、および現在の移動数mがあれば、再帰アルゴリズムに頼ることなく、最適なソリューションですべてのディスクの位置を復元できます。
ハノイの塔の問題のバリエーション、特に4本以上の棒の場合に興味がある人のために、 PapaBubaDiopの経験に慣れることをお勧めします。PapaBubaDiopはゲームの形でこの方向を発展させ 、同時に異なるプラットフォームでいくつかのバージョンを収益化しようとします。
大量の入力データと計算リソースを使用するこのような問題に対してより最適化された理論的解決策に興味のある読者にとって、この出版物が今後の成果の基礎として役立つことを願っています。
スタイルと言語は少し乾燥しており、アカデミックな仕事に適しています。したがって、特にカルマをまっすぐにしてマイナスから抜け出す試みを考慮して、あまり厳しく判断しないでください。 すべての最高の明るい2017
UPD：コメント、コメント、ヒントをありがとうございます。 上記のアルゴリズムに従って動作するスクリプトの例は、 このリンクで入手できます。 GMPライブラリは、大量の作業をサポートするために使用されました。