ハノイ塔のアルゴリズム: Python, C++ Code
ハノイの塔とは何ですか?
ハノイの塔は、1883 本の棒と積み重ねられた多数の円盤で構成される数学パズルです。 これは、フランスの数学者エドゥアール ルーカスが XNUMX 年に紹介したため、ブラフマの塔またはルーカスの塔としても知られています。このパズルは、XNUMX 本の棒の間で金の円盤を動かすという伝説に基づいています。
このパズルには XNUMX 本の棒と、可変の数の積み重ねられたディスクが含まれています。 これらのロッドは環状の塔として設計されています。 したがって、直径の大きなディスクが下に積み重ねられ、小さなディスクが上に積み重ねられます。
最初に、XNUMX本のペグまたはロッドが与えられます。 そしてそのうちの XNUMX つ (例では A) にはすべてのディスクがスタックされています。 いくつかの特定のルールに従って、ディスクのスタック全体を XNUMX つのロッド (A) から別のロッド (C) に移動することを目的としています。
パズルの初期設定は次のとおりです。
そしてこれが最終目標です -
ハノイ塔のルール
ハノイ塔の重要なルールは次のとおりです。
- このパズルの初期状態では、すべてのディスクがロッド XNUMX に積み重ねられます。
- 最終的な状態は、ロッド XNUMX のすべてのディスクがロッド XNUMX またはロッド XNUMX の上に積み重ねられることです。
- いつでもディスク上のロッドをあるロッドから別のロッドに移動できます。
- ロッドから移動できるのは最上部のディスクだけです。
- ディスクは、より小さい別のディスクの上に配置することはできません。
元々の伝説は、64 枚のディスクを動かすというものでした。僧侶たちは、ルールに従って一度に 2 枚のディスクを動かすことができました。伝説によると、僧侶たちがその行為を成し遂げることができれば世界が終わるという予言がありました。時間計算量のセクションでは、ハノイの塔の n 枚のディスクの設定には 1^n – XNUMX 回の移動が必要であることを示します。
したがって、僧侶がディスクを動かすのに 1 秒しかかからないとすると、パズルを解くのに必要な合計時間は 2^64 - 1 秒、つまり 584,942,417,356 年、26 日、7 時間、15 秒になります。
ハノイ塔のアルゴリズム
ハノイ塔を解決する一般的な方法の XNUMX つは再帰アルゴリズムです。 まず、移動元と移動先として XNUMX 本のロッドまたはペグを決定する必要があります。予備のペグは補助またはヘルパーとなります。
ハノイの塔パズルを解く手順は次のとおりです。
- 上位 n-1 個のディスクをソース ペグからヘルパー ペグに移動します。
- その後、n 番目のディスクをソース ペグから宛先ペグに移動します。
- 最後に、残りの n-1 個のディスクをヘルパー ペグから宛先ペグに移動します。
注意: 単一のディスクがある場合は、ソースから宛先に直接移動できます。
ハノイの塔パズルの解き方
XNUMX つのディスクのアルゴリズムを説明し、ペグ A をソース、ペグ B をヘルパー、ペグ C を宛先として考えてみましょう。
ステップ1) 最初は、すべてのディスクがペグ A に積み重ねられます。
この段階では:
ソース = ペグ A
目的地 = ペグ C
ヘルパー = ペグ B
次に、上位 n-1 個のディスクをソースからヘルパーに移動する必要があります。
ご注意: 一度に移動できるディスクは 3 つだけですが、これにより、問題は 2 つのディスクの問題から XNUMX つのディスクの問題に分割されます。これは再帰呼び出しです。
ステップ2) ペグ A から再帰呼び出しを呼び出し、宛先がペグ B であるため、ペグ C をヘルパーとして使用します。
XNUMX つのディスクに対する同じハノイの塔問題のステージ XNUMX に戻っていることに注意してください。
ここで、n-1 個または XNUMX 個のディスクをソースからヘルパーに移動し、最小のディスクをペグ A からペグ C に移動する必要があります。
この段階では:
ソース = ペグ A
目的地 = ペグ B
ヘルパー = ペグ C
ステップ3) 次に、私たちのアルゴリズムに従って、n 番目または 2 番目のディスクのニーズを宛先またはペグ B に転送する必要があります。
この段階では:
ソース = ペグ A
目的地 = ペグ B
ヘルパー = ペグ C
ステップ4) ここで、アルゴリズムの第 1 段階に従って、n-XNUMX 個のディスクまたはディスク XNUMX をヘルパーまたはペグ C から宛先またはペグ B に移動します。
この段階では:
ソース = ペグ A
目的地 = ペグ B
ヘルパー = ペグ C
ステップ5) 再帰呼び出しが完了すると、アルゴリズムの最初の段階での以前の設定に戻ります。
ステップ6) 次に、第 3 段階では、ソースを宛先に移動します。つまり、ディスク XNUMX をペグ A からペグ C に移動します。
この段階では:
ソース = ペグ A
目的地 = ペグ C
ヘルパー = ペグ B
ステップ7) 今ではそれがわかります
d は、残りのディスクをヘルパー (ペグ B) から宛先 (ペグ C) に移動することです。 この場合、最初のソースまたはペグ A をヘルパーとして使用します。
ステップ8) 1つのディスクを同時に動かすことはできないので、ディスクXNUMXの再帰呼び出しを呼び出します。最後のステップと アルゴリズム、このステップの宛先はペグ A です。
この段階では:
ソース = ペグ B
目的地 = ペグ A
ヘルパー = ペグ C
ステップ9) これで再帰呼び出しは完了しました。 次に、ディスク 2 をソースから宛先に移動します。
この段階では:
ソース = ペグ B
目的地 = ペグ C
ヘルパー = ペグ A
ステップ10) 次に、残りの n-1 またはディスク 1 をヘルパーから宛先に移動します。
この段階では:
ソース = ペグ A
目的地 = ペグ C
ヘルパー = ペグ B
ハノイ塔の疑似コード
START Procedure Tower_Of_Hanoi(disk, source, dest, helper) IF disk == 1, THEN move disk from source to dest ELSE Tower_Of_Hanoi (disk - 1, source, helper, dest) move disk from source to dest Tower_Of_Hanoi (disk - 1, helper, dest, source) END IF END Procedure
プログラムコード C++
#include <bits/stdc++.h> using namespace std; void tower_of_hanoi(int num, string source, string dest, string helper) { if (num == 1) { cout << " Move disk 1 from tower " << source << " to tower " << dest << endl; return; } tower_of_hanoi(num - 1, source, helper, dest); cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl; tower_of_hanoi(num - 1, helper, dest, source); } int main() { int num; cin >> num; printf("The sequence of moves :\n"); tower_of_hanoi(num, "I", "III", "II"); return 0; }
出力
3 The sequence of moves : Move disk 1 from tower I to tower III Move disk 2 from tower I to tower II Move disk 1 from tower III to tower II Move disk 3 from tower I to tower III Move disk 1 from tower II to tower I Move disk 2 from tower II to tower III Move disk 1 from tower I to tower III
プログラムコード Python
def tower_of_hanoi(n, source, destination, helper): if n==1: print ("Move disk 1 from peg", source," to peg", destination) return tower_of_hanoi(n-1, source, helper, destination) print ("Move disk",n," from peg", source," to peg", destination) tower_of_hanoi(n-1, helper, destination, source) # n = number of disks n = 3 tower_of_hanoi(n,' A','B','C')
出力:
Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B
ハノイの塔の複雑さ
ハノイの塔の時間と空間の複雑さは次のとおりです。
1) 時間計算量:
アルゴリズムを振り返ると、(n-1) 個のディスクに対する再帰呼び出しを 1 回導入していることがわかります。 (n-1) 個のディスクに対する再帰呼び出しは、移動するディスクが 1 つだけになるまで、他の ((n-XNUMX)-XNUMX) などに分割できます。
ディスク XNUMX 枚の場合、
- ディスク 3 は、ディスク XNUMX の再帰関数を XNUMX 回呼び出します。
- ディスク 2 は、ディスク XNUMX の再帰関数を XNUMX 回呼び出します。
- ディスク 1 は一定の時間内に移動でき、XNUMX つのディスクを解決するのに時間がかかります。
= 2*(3 つのディスクを解決する時間) + 定数 ディスク XNUMX を移動する時間
= 2*(2*2 つのディスクを解決する時間 + 定数 ディスク 3 を移動する時間) + 定数 ディスク XNUMX を移動する時間
= (2*2) (ディスク 1 を移動するための一定時間) + 2* ディスク 2 を移動するための一定時間 + ディスク 3 を移動するための一定時間
n 個のディスクの場合、次のように記述できます –
(2n-1 * ディスク 1 + 2 を移動する定数時間n-2 * ディスク 2 + …を移動するための一定時間。
この等比数列の結果は O(2n-1)または O(2n), それは指数関数的です。
2) 空間の複雑さ
ハノイの塔の空間計算量は 0(n) です。これは、プレートのシーケンスを格納する必要があるためです。再帰を使用する場合、スタックを使用します。スタックの最大サイズは「n」です。そのため、空間計算量は O(n) になります。