データ構造とアルゴリズム-ハノイの塔

ハノイの塔は、3つの塔（ペグ）で構成される数学パズルであり、複数のリングが描かれているとおりです-

これらのリングはサイズが異なり、昇順で積み重ねられます。つまり、小さい方のリングが大きい方のリングの上に配置されます。ディスクの数が増えるパズルの他のバリエーションがありますが、タワーの数は同じままです。

ルール

使命は、配置の順序に違反することなく、すべてのディスクを別のタワーに移動することです。ハノイの塔が従うべきいくつかのルールは次のとおりです。

タワー間で一度に移動できるディスクは1つだけです。
「トップ」ディスクのみを取り外すことができます。
大きなディスクを小さなディスクの上に置くことはできません。

以下は、3つのディスクでハノイの塔のパズルを解くアニメーション表現です。

n個のディスクを持つハノイの塔パズルは最小限で解決できます 2ⁿ−1ステップ。このプレゼンテーションは、3つのディスクを持つパズルが取ったことを示しています2³ - 1 = 7 ステップ。

アルゴリズム

ハノイの塔のアルゴリズムを作成するには、最初に、より少ないディスク数、たとえば→1または2でこの問題を解決する方法を学ぶ必要があります。3つのタワーに名前を付けます。 source、 destination そして aux（ディスクの移動を支援するためのみ）。ディスクが1つしかない場合は、ソースペグからデスティネーションペグに簡単に移動できます。

ディスクが2つある場合-

まず、小さい方の（上部の）ディスクを補助ペグに移動します。
次に、大きい方の（下の）ディスクを宛先ペグに移動します。
そして最後に、小さい方のディスクをauxから宛先ペグに移動します。

これで、3つ以上のディスクを備えたハノイの塔のアルゴリズムを設計できるようになりました。ディスクのスタックを2つの部分に分割します。最大のディスク（n^番目のディスク）は1つの部分にあり、他のすべての（n-1）ディスクは2番目の部分にあります。

私たちの究極の目的は、ディスクを移動することです nソースからデスティネーションへ、そして他のすべての（n1）ディスクをその上に置きます。与えられたすべてのディスクセットに同じものを再帰的に適用することを想像できます。

従う手順は次のとおりです。

Step 1 − Move n-1 disks from source to aux
Step 2 − Move n^th disk from source to dest
Step 3 − Move n-1 disks from aux to dest

ハノイの塔の再帰的アルゴリズムは、次のように駆動できます。

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Cプログラミングでの実装を確認するには、ここをクリックしてください。