Ziel des Spiels ist es, den kompletten Ring-Stapel von einem Stab auf einen anderen Stab zu versetzen.
Hierbei gelten 2 Regeln:
1. Es darf immer nur ein Ring gleichzeitig bewegt werden.
2. Der bewegte Ring darf nicht auf einen kleineren Ring gesteckt werden.
Die Lösung ist ein klassisches Beispiel für eine rekursive Vorgehensweise.
Die Parameter sind:
n Anzahl der Ringe
Quelle (1. Stab)
Ziel (2. Stab) und
Via (3. Stab)
Der letzte Parameter ist eigentlich überflüssig, denn er kann aus Quelle und Ziel errechnet werden
Lösungsalgorithmus:
Falls n > 0
Bringe n-1 Ringe von der Quelle nach Via
Bringe 1 Ring von der Quelle nach Ziel
Bringe n-1 Ringe von Via nach Ziel
Sei hanoi eine Funktion mit den angegebenen Parametern. Dann lässt sich die Funktion darstellen
durch:
function hanoi(n,Quelle, Ziel, Via) {
if (n>0) {
hanoi(n-1,Quelle,Via,Ziel)
bringe 1 Ring von Quelle nach Ziel
hanoi(n-1,Via,Ziel,Quelle)
}
}
Man erkennt, die Funktion hanoi ruft sich selbst wieder auf. Da die Anzahl n bei jedem Aufruf um 1
verringert wird, wird nach (2⋅n - 1) - Aufrufen ein Abbruch erreicht.
Die Anzahl der Aufrufe lässt sich durch vollständige Induktion (s. unter
Mathematik->Allgemeines->Beweisverfahren) bestimmen.
Geschichtliches:
Das Spiel wurde 1883 vom französischen Mathematiker Édouard Lucas erfunden – deshalb auch manchmal
Lucas-Türme genannt.
Lucas brachte das Spiel 1883 auf den Markt als Tour d’Hanoi von einem Prof. Claus aus Siam (von der
Universität Li-Sou-Stian), ein Anagramm für Lucas und die Universität Saint-Louis.
Er dachte sich dazu die Geschichte aus, dass dies eine vereinfachte Version des Turms von Brahma sei.
Indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, müssten einen Turm aus 64 goldenen
Scheiben versetzen.
Bevor ihnen das gelungen sei, wäre aber der Tempel zu Staub zerfallen und mit einem Donnerschlag das Ende
der Welt gekommen.