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

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

ハノイの塔

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

規則

ミッションは、配列の順序に違反することなく、すべてのディスクを別のタワーに移動することです。ハノイの塔のために従うべきいくつかのルールは-

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

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

ハノイの塔

n個のディスクを備えたハノイの塔パズルは、最小 2 ^ n ^ -1 ステップで解決できます。このプレゼンテーションは、3個のディスクを使用したパズルが 2 ^ 3 ^-1 = 7 ステップを踏んだことを示しています。

アルゴリズム

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

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

最初に、小さい（上部）ディスクを補助ペグに移動します。
次に、大きい（下）ディスクを目的のペグに移動します。
最後に、小さいディスクを補助ペグから目的のペグに移動します。

2つのディスクを備えたハノイの塔

そのため、現在、3枚以上のディスクでハノイの塔のアルゴリズムを設計する立場にあります。ディスクのスタックを2つの部分に分割します。最大のディスク（n ^ th ^ディスク）は1つの部分にあり、他のすべての（n-1）ディスクは2番目の部分にあります。

最終的な目的は、ディスクをソースからデスティネーションに n 移動し、他のすべての（n1）ディスクをそのディスクに配置することです。与えられたすべてのディスクセットに対して同じ方法を再帰的に適用することを想像できます。

従うべき手順は次のとおりです-

Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth 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プログラミングでの実装を確認するには、リンク：/data_structures_algorithms/tower_of_hanoi_in_c [ここをクリック]。

Data-structures-algorithms-tower-of-hanoi

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

規則

アルゴリズム