Turm von Hanoi-Algorithmus: Python, C++ Code

⚡ Intelligente Zusammenfassung

Der Turm von Hanoi ist ein klassisches rekursives Puzzle, bei dem ein Stapel Scheiben zwischen drei Stäben hin und her bewegt wird, wobei niemals eine größere Scheibe auf eine kleinere gelegt wird. Dies veranschaulicht das Prinzip „Teile und herrsche“ deutlich.

🗼 Puzzle-Setup: Drei Stifte und n Scheiben sind in abnehmender Größe auf dem Quellstift gestapelt und warten darauf, mithilfe eines Hilfsstifts zum Zielstift bewegt zu werden.
📜 Regeln: Es kann immer nur eine Scheibe bewegt werden, nur die oberste Scheibe eines jeden Stifts kann sich bewegen, und eine größere Scheibe kann nicht auf einer kleineren Scheibe ruhen.
🔁 Rekursive Idee: Bewege n-1 Scheiben auf den Hilfsstift, bewege die größte Scheibe auf den Zielstift und bewege dann die n-1 Scheiben vom Hilfsstift zum Zielstift.
️ Zeitliche Komplexität: Das Lösen von n Scheiben erfordert 2^n – 1 Züge, was zu einer exponentiellen Zeitkomplexität von O(2^n) führt, die mit zunehmendem n sehr schnell ansteigt.
🧠 Raumkomplexität: Der Rekursionsstapel kann bis zu n Frames gleichzeitig speichern, daher beträgt die Speicherkomplexität der rekursiven Lösung O(n).
️ Anwendungen: Vermittlung von Rekursion, Backup-Rotationsverfahren, stackbasierter Datenbewegung, Robotersequenzierung und Verständnis des Divide-and-Conquer-Algorithmusdesigns.

Was ist der Turm von Hanoi?

Der Turm von Hanoi ist ein mathematisches Rätsel, bestehend aus drei Stäben und einem Stapel von Scheiben abnehmender Größe, die übereinander gestapelt sind. Er ist auch als Turm von Brahma oder Lucas-Turm bekannt, da der französische Mathematiker Édouard Lucas ihn 1883 einführte. Das Rätsel basiert auf Legenden über das Verschieben von Goldscheiben zwischen drei Stäben.

Dieses Puzzle besteht aus drei Stäben und einer variablen Anzahl gestapelter Scheiben. Die Stäbe sind wie kreisförmige Türme angeordnet, wobei die größeren Scheiben unten und die kleineren Scheiben oben gestapelt sind.

Zunächst erhalten wir drei Stäbe oder Stangen. Auf einem davon (im Beispiel Stab A) sind alle Scheiben gestapelt. Ziel ist es, den gesamten Stapel unter Einhaltung bestimmter Regeln von Stab A auf Stab C zu bewegen.

Hier ist der Ausgangsaufbau des Puzzles:

Turm von Hanoi-Problem

Und das ist das Endziel:

Regeln des Turms von Hanoi

Hier sind die wichtigsten Regeln für den Turm von Hanoi:

Im Ausgangszustand des Puzzles sind alle Scheiben auf Stab eins gestapelt.
Im Endzustand sind alle Scheiben von Stab eins auf Stab zwei oder Stab drei gestapelt.
Es kann immer nur eine Scheibe von einem Stab zum anderen wandern.
Nur die oberste Scheibe auf einer Stange kann bewegt werden.
Eine Scheibe kann nicht auf eine kleinere Scheibe gelegt werden.

Die ursprüngliche Legende handelte vom Bewegen von 64 Scheiben. Die Priester durften gemäß den Regeln jeweils eine Scheibe bewegen. Der Legende zufolge prophezeite man, dass die Welt untergehen würde, wenn ihnen dies gelänge. Im Abschnitt zur Zeitkomplexität zeigen wir, dass ein Turm von Hanoi mit n Scheiben 2^n – 1 Bewegungen erfordert.

Wenn die Priester also 1 Sekunde benötigten, um eine Scheibe zu bewegen, würde die Gesamtzeit zur Lösung des Rätsels 2^64 – 1 Sekunden betragen, also ungefähr 584,942,417,356 Jahre, 26 Tage, 7 Stunden und 15 Sekunden.

Algorithmus für den Turm von Hanoi

Die gebräuchlichste Methode zur Lösung des Turms von Hanoi ist ein rekursiver Algorithmus. Zuerst wählt man zwei Stäbe als Start- und Zielstab; der übrige Stab dient als Hilfsstab.

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.
Verschiebe die n-te Scheibe vom Quellstift zum Zielstift.
Verschiebe die verbleibenden n-1 Scheiben vom Hilfsstift zum Zielstift.

Hinweis: Wenn wir nur eine Festplatte haben, können wir sie direkt von der Quelle zum Ziel verschieben.

So lösen Sie das Turm-von-Hanoi-Rätsel

Wir wollen den Algorithmus anhand von drei Scheiben veranschaulichen. Stift A sei die Quelle, Stift B der Helfer und Stift C das Ziel.

Schritt 1) Anfangs sind alle Scheiben auf Stift A gestapelt.

In dieser Phase: 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 immer nur eine Scheibe gleichzeitig bewegen können, reduziert dieser Schritt unser 3-Scheiben-Problem auf ein 2-Scheiben-Problem, das durch einen rekursiven Aufruf gelöst wird.

Schritt 2) Wenn wir von Peg A aus einen rekursiven Aufruf mit Peg B als Ziel durchführen, verwenden wir Peg C als Hilfsknoten.

Beachten Sie, dass wir uns wieder in Phase eins des Turm-von-Hanoi-Problems befinden, diesmal jedoch mit zwei Scheiben. Wir bewegen n-1 (also eine) Scheibe vom Startpunkt zum Hilfspunkt, wodurch die kleinste Scheibe von Stab A zu Stab C bewegt wird.

In dieser Phase: Quelle = Stift A, Ziel = Stift B, Helfer = Stift C.

Schritt 3) Gemäß dem Algorithmus wird nun die n-te (2.) Scheibe an den Zielpunkt, Steckplatz B, übertragen.

In dieser Phase: Quelle = Stift A, Ziel = Stift B, Helfer = Stift C.

Schritt 4) Nun bewegen wir die n-1-te Scheibe (Scheibe eins) vom Hilfsstift C zum Zielstift B, gemäß dem dritten Schritt des Algorithmus.

In dieser Phase: Quelle = Stift A, Ziel = Stift B, Helfer = Stift C.

Schritt 5) Nach Abschluss des rekursiven Aufrufs kehren wir zu unserer vorherigen Einstellung in der ersten Phase des Algorithmus zurück.

Schritt 6) Im zweiten Schritt bewegen wir die Scheibe 3 vom Quellanschluss A zum Zielanschluss C.

In dieser Phase: Quelle = Stift A, Ziel = Stift C, Helfer = Stift B.

Schritt 7) Die nächste Aufgabe besteht darin, die verbleibenden Scheiben vom Hilfsteller (Stift B) zum Zielteller (Stift C) zu bewegen. Diesmal verwenden wir den ursprünglichen Quellteller (Stift A) als Hilfsteller.

Schritt 8) Da wir nicht zwei Datenträger gleichzeitig bewegen können, führen wir einen rekursiven Aufruf für Datenträger 1 durch. Laut unserer AlgorithmusDas Ziel in diesem Schritt ist Pfosten A.

In dieser Phase: Quelle = Stift B, Ziel = Stift A, Helfer = Stift C.

Schritt 9) Unser rekursiver Aufruf ist abgeschlossen. Wir verschieben nun Datenträger 2 von seinem Quell- zum Zieldatenträger.

In dieser Phase: Quelle = Stift B, Ziel = Stift C, Helfer = Stift A.

Schritt 10) Zum Schluss verschieben wir die verbleibende n-1-Disk (Disk 1) vom Hilfs- zum Zielsystem.

In dieser Phase: Quelle = Stift A, Ziel = Stift C, Helfer = Stift B.

Spitzname Code 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 die zeitliche und räumliche Komplexität des Turms von Hanoi:

1) Zeitliche Komplexität:

Betrachtet man den Algorithmus, so wird er bei jedem Aufruf zweimal rekursiv für (n-1) Scheiben aufgerufen. Jede (n-1)-te Rekursion zerfällt in ((n-1)-1)-te Rekursionen usw., bis man den Basisfall mit einer einzigen Scheibe erreicht.

Für drei Disketten:

Disk 3 ruft die rekursive Funktion für Disk 2 zweimal auf.
Disk 2 ruft die rekursive Funktion für Disk 1 zweimal auf.
Scheibe 1 bewegt sich in konstanter Zeit, wodurch genügend Zeit bleibt, um die Gleichung für drei Scheiben zu lösen.

Als wiederkehrendes Ereignis ausgedrückt:

= 2 × (Zeit zum Berechnen der beiden Scheiben) + konstante Zeit zum Bewegen der Scheibe 3

= 2 × (2 × Zeit zum Berechnen einer Scheibe + konstante Zeit zum Bewegen der zweiten Scheibe) + konstante Zeit zum Bewegen der dritten Scheibe

= (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 ergibt sich Folgendes:

2^n-1 × konstante Zeit zum Bewegen der Scheibe 1 + 2^n-2 × konstante Zeit zum Bewegen der Scheibe 2 + ….

Diese geometrische Folge summiert sich zu O(2ⁿ – 1), was sich vereinfacht zu O (2ⁿ), eine exponentielle Zeitkomplexität.

2) Speicherkomplexität:

Die Speicherkomplexität des Turms von Hanoi beträgt O(n). Die Rekursion nutzt den Aufrufstapel, dessen maximale Tiefe n, der Anzahl der Scheiben, entspricht. Daher ist die Speicherkomplexität O(n).

Häufig gestellte Fragen

Der Turm-von-Hanoi-Algorithmus ist ein rekursives Verfahren, das n Scheiben von einem Startpunkt zu einem Zielpunkt bewegt, indem es einen Hilfspunkt verwendet, wobei niemals eine größere Scheibe auf eine kleinere gelegt wird.

Die minimale Anzahl an Zügen für n Scheiben beträgt 2^n – 1. Drei Scheiben benötigen 7 Züge, vier Scheiben benötigen 15 Züge und zehn Scheiben benötigen 1,023 Züge.

Die Zeitkomplexität beträgt O(2^n), da jede zusätzliche Scheibe den Arbeitsaufwand verdoppelt. Die Rekursionsgleichung T(n) = 2T(n-1) + 1 ergibt 2^n – 1, was exponentiell ist.

Die Speicherkomplexität beträgt O(n), da der Rekursionsaufrufstapel für jede verarbeitete Festplatte einen Frame speichert. Die maximale Rekursionstiefe beträgt n, daher ist der benötigte Zusatzspeicher linear in der Anzahl der Festplatten.

Ja. Eine iterative Lösung verwendet eine Schleife mit einem festen Muster: Bei ungeraden Zügen wird die kleinste Scheibe zyklisch zwischen den Stäben getauscht, und bei geraden Zügen wird der einzig zulässige Zug, der nicht die kleinste Scheibe ist, ausgeführt.

Der Algorithmus lehrt Rekursion, modelliert Backup-Rotationsschemata für die Speicherung, steuert die Sequenzierung von Roboterarmen und taucht in neuropsychologischen Tests auf, die die Planungsfähigkeit messen.

Agenten für bestärkendes Lernen lösen den Turm von Hanoi, indem sie jede Scheibenkonfiguration als Zustand und jeden Zug als Aktion behandeln. Er dient als gängiger Benchmark für Planung und hierarchisches Strategielernen.

Ja. GitHub Copilot, ChatGPT und Gemini Rekursive Lösungen für den Turm von Hanoi generieren in Python, C++ und JavaDie Entwickler sollten dennoch die Basisfälle und die Argumentreihenfolge überprüfen.

Turm von Hanoi-Algorithmus: Python, C++ Code

Was ist der Turm von Hanoi?

Regeln des Turms von Hanoi

Algorithmus für den Turm von Hanoi

So lösen Sie das Turm-von-Hanoi-Rätsel

Spitzname Code für den Turm von Hanoi

Programmcode in C++

Programmcode in Python

Komplexität des Turms von Hanoi

Häufig gestellte Fragen

Fassen Sie diesen Beitrag mit folgenden Worten zusammen:

Melden Sie sich für den Newsletter an