Turm von Hanoi-Algorithmus: Python, C++ Code
Sarah Chen
Was ist der Turm von Hanoi?
Der Turm von Hanoi ist ein mathematisches Puzzle, das aus drei übereinander angeordneten Stäben und zahlreichen Scheiben besteht. Er ist auch als Turm von Brahma oder Lucas-Turm bekannt, da der französische Mathematiker Edouard Lucas ihn bereits 1883 vorstellte. Dieses Rätsel basiert auf Legenden über die Bewegung von Goldscheiben zwischen drei Stäben.
Dieses Puzzle besteht aus drei Stäben und einer variablen Anzahl gestapelter Scheiben. Diese Stäbe sind als zyklische Türme konzipiert. Daher werden die Scheiben mit dem größeren Durchmesser unten und die Scheiben mit kleinerem Durchmesser oben gestapelt.
Zunächst erhalten wir drei Stifte oder Stangen. Und auf einem von ihnen (A, im Beispiel gezeigt) sind alle Festplatten gestapelt. Unser Ziel ist es, einen ganzen Scheibenstapel von einem Stab (A) zu einem anderen (C) zu bewegen, indem wir bestimmte Regeln befolgen.
Hier ist der anfängliche Aufbau des Puzzles:
Und das ist das Endziel-
Regeln des Turms von Hanoi
Hier sind einige wesentliche Regeln für den Turm von Hanoi:
- Im Ausgangszustand dieses Puzzles sind alle Scheiben in Stab eins gestapelt.
- Der Endzustand ist, dass alle Scheiben von Stab eins auf Stab zwei oder Stab drei gestapelt werden.
- Wir können eine On-Disk jederzeit von einem Stab zum anderen verschieben.
- Wir können nur die oberste Scheibe von der Stange bewegen.
- Eine Festplatte kann nicht über eine andere, kleinere Festplatte gelegt werden.
In der ursprünglichen Legende ging es um das Verschieben von 64 Scheiben. Den Regeln entsprechend konnten die Priester jeweils eine Scheibe verschieben. Der Legende zufolge gab es eine Prophezeiung, dass die Welt untergehen würde, wenn sie die Tat vollenden könnten. Im Abschnitt zur Zeitkomplexität werden wir zeigen, dass eine Einstellung des Turms von Hanoi mit n Scheiben 2^n – 1 Bewegung kosten würde.
Wenn die Priester also 1 Sekunde benötigen würden, um die Scheiben zu bewegen, wäre die Gesamtzeit, die sie zum Lösen des Rätsels benötigen würden, 2^64 – 1 Sekunde oder 584,942,417,356 Jahre, 26 Tage, 7 Stunden und 15 Sekunden.
Algorithmus für den Turm von Hanoi
Eine allgemeine Möglichkeit, den Turm von Hanoi zu lösen, ist ein rekursiver Algorithmus. Zuerst müssen wir uns für zwei Stäbe oder Stifte als Quelle und Ziel entscheiden, und der Ersatzstift wäre ein Hilfsmittel oder Helfer.
Hier sind die Schritte, um das Turm-von-Hanoi-Rätsel zu lösen:
- Verschieben Sie die oberen n-1 Scheiben vom Quellstift zum Hilfsstift.
- Anschließend verschieben Sie die n-te Festplatte vom Quell-Peg zum Ziel-Peg.
- Zum Schluss verschieben Sie die restlichen n-1 Festplatten vom Hilfsstift zum Zielstift.
Note: Wenn wir eine einzelne Festplatte haben, können wir sie direkt von der Quelle zum Ziel verschieben.
So lösen Sie das Turm-von-Hanoi-Rätsel
Lassen Sie uns den Algorithmus für drei Festplatten veranschaulichen und betrachten wir Peg A als Quelle, Peg B als Helfer und Peg C als Ziel
Schritt 1) Zunächst werden alle Scheiben auf Stift A gestapelt.
In diesem Stadium:
Quelle = Peg A
Ziel = Peg C
Helfer = Peg B
Jetzt müssen wir die obersten n-1 Festplatten von der Quelle auf den Helfer verschieben.
Hinweis: Obwohl wir jeweils nur eine Platte verschieben können, wird dadurch unser Problem von einem 3-Platten-Problem in ein 2-Platten-Problem umgewandelt, was einen rekursiven Aufruf darstellt.
Schritt 2) Da wir einen rekursiven Aufruf von Peg A aus aufrufen und das Ziel Peg B ist, verwenden wir Peg C als Helfer.
Beachten Sie, dass wir uns wieder bei der ersten Stufe des gleichen Turm-von-Hanoi-Problems für zwei Festplatten befinden.
Jetzt müssen wir n-1 oder eine Scheibe von der Quelle zum Helfer verschieben und dabei die kleinste Scheibe von Stift A nach Stift C verschieben.
In diesem Stadium:
Quelle = Stift A
Ziel = Stift B
Helfer = Stift C
Schritt 3) Dann sollte gemäß unserem Algorithmus der n-te oder 2. Festplattenbedarf in das Ziel oder Peg B übertragen werden.
In diesem Stadium:
Quelle = Stift A
Ziel = Stift B
Helfer = Stift C
Schritt 4) Nun verschieben wir gemäß der dritten Stufe unseres Algorithmus die n-1 Festplatten oder Festplatte eins von Helfer oder Stift C zum Ziel oder Stift B.
In diesem Stadium:
Quelle = Stift A
Ziel = Stift B
Helfer = Stift C
Schritt 5) Nach Abschluss des rekursiven Aufrufs kehren wir in der ersten Stufe des Algorithmus zu unserer vorherigen Einstellung zurück.
Schritt 6) Jetzt, in der zweiten Stufe, verschieben wir unsere Quelle zu unserem Ziel, das heißt, wir verschieben Platte 3 von Stift A auf Stift C.
In diesem Stadium:
Quelle = Stift A
Ziel = Stift C
Helfer = Stift B
Schritt 7) Jetzt können wir das sehen
d besteht darin, die verbleibenden Festplatten vom Helfer (Stift B) zum Ziel (Stift C) zu verschieben. In diesem Fall verwenden wir die ursprüngliche Quelle oder Stift A als Hilfsmittel.
Schritt 8) Da wir nicht zwei Platten gleichzeitig verschieben können, führen wir einen rekursiven Aufruf für Platte 1 durch. Gemäß dem letzten Schritt und unserer Algorithmus, ein Ziel in diesem Schritt ist Stift A.
In diesem Stadium:
Quelle = Stift B
Ziel = Stift A
Helfer = Stift C
Schritt 9) Unser rekursiver Aufruf ist nun abgeschlossen. Dann verschieben wir Datenträger 2 von seiner Quelle zu seinem Ziel.
In diesem Stadium:
Quelle = Stift B
Ziel = Stift C
Helfer = Stift A
Schritt 10) Dann verschieben wir unser verbleibendes n-1 oder Laufwerk 1 vom Helfer zum Ziel.
In diesem Stadium:
Quelle = Stift A
Ziel = Stift C
Helfer = Stift B
Pseudocode für den Turm von Hanoi
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
Programmcode in 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;
}
Ausgang
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
Programmcode in 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')
Ausgang:
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
Komplexität des Turms von Hanoi
Hier sind die zeitliche und räumliche Komplexität des Turms von Hanoi:
1) Zeitliche Komplexität:
Wenn wir auf unseren Algorithmus zurückblicken, können wir erkennen, dass wir zweimal einen rekursiven Aufruf für (n-1) Festplatten einführen. Diese rekursiven Aufrufe für (n-1) Festplatten können in andere ((n-1)-1) usw. zerlegt werden, bis nur noch eine Festplatte bewegt werden kann.
Für drei Festplatten-
- Datenträger 3 ruft zweimal eine rekursive Funktion für Datenträger zwei auf.
- Datenträger 2 ruft zweimal eine rekursive Funktion für Datenträger eins auf.
- Scheibe 1 kann sich innerhalb einer konstanten Zeit und Zeit bewegen, um drei Scheiben zu lösen.
= 2*(Zeit zum Lösen zweier Scheiben) + konstante Zeit zum Verschieben von Scheibe 3
= 2*(2*Zeit zum Lösen einer Scheibe + konstante Zeit zum Verschieben von Scheibe 2) + konstante Zeit zum Verschieben von Scheibe 3
= (2*2) (konstante Zeit zum Bewegen von Scheibe 1) + 2*konstante Zeit zum Bewegen von Scheibe 2 + konstante Zeit zum Bewegen von Scheibe 3
Für n Festplatten kann es geschrieben werden als –
(2n-1 * konstante Zeit zum Bewegen von Scheibe 1 + 2n-2 * konstante Zeit zum Bewegen von Scheibe 2 + ….
Dieser geometrische Verlauf führt zu O(2n-1oder O (2n), was exponentiell ist.
2) Raumkomplexität
Die Speicherkomplexität des Turms von Hanoi beträgt 0(n). Das liegt daran, dass wir die Reihenfolge der Platten speichern müssen. Wenn wir die Rekursion verwenden, verwenden wir den Stapel. Und die maximale Größe des Stapels kann „n“ sein. Deshalb wird die Speicherkomplexität O(n).
