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

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