Die Türme von Hanoi tauchen fast immer auf, wenn man beim Programmieren die „Rekursion“ lernt. Von Hand brauchen sie Hunderte von Zügen, als Programm sind sie in wenigen Zeilen geschrieben. Sehen wir uns Schritt für Schritt an, wie das funktioniert. Die Stäbe heißen links, Mitte und rechts, und die Scheiben sind von der kleinsten an mit 1, 2, 3 … nummeriert.
Was ist Rekursion?
Rekursion bedeutet, dass man beim Lösen eines Problems dasselbe Verfahren auf ein kleineres Problem anwendet. Wenn man das Problem immer weiter verkleinert, kommt man irgendwann zu einem, dessen Antwort sofort feststeht (bei 0 Scheiben tut man zum Beispiel nichts), und dort hört es auf.
Die Türme von Hanoi rekursiv denken
Wir wollen einen Turm aus n Scheiben von links nach rechts bewegen.
- Die oberen n − 1 Scheiben von links in die Mitte bringen.
- Die größte Scheibe n von links nach rechts bewegen.
- Die n − 1 Scheiben aus der Mitte nach rechts bringen.
Schritt 1 und 3 sind das Problem „einen Turm aus n − 1 Scheiben bewegen“, das dieselbe Form hat wie das ursprüngliche Problem. Nur die Stäbe, von denen und auf die bewegt wird, sind andere. Schreibt man also ein einziges Verfahren „n Scheiben von einem Stab auf einen anderen bewegen, mit dem übrigen Stab als Hilfe“, kann es sich darin selbst aufrufen.
Pseudocode
Prozedur hanoi(n, von, nach, hilf):
wenn n gleich 0 ist, nichts tun und fertig
hanoi(n − 1, von, hilf, nach) … die oberen n−1 Scheiben beiseite bringen
Scheibe n von „von“ nach „nach“ bewegen
hanoi(n − 1, hilf, nach, von) … die n−1 Scheiben zurückbringen
hanoi(3, links, rechts, Mitte) liefert die Züge für 3 Scheiben von links nach rechts Allein damit erhält man für jede Scheibenzahl die Zugfolge mit den wenigsten Zügen. Lauffähigen Code in Python und C findest du in Die Türme von Hanoi in Python und C lösen.
Wie sich die Aufrufe verzweigen
Schreibt man für 3 Scheiben auf, wie hanoi aufgerufen wird, entsteht ein Baum wie dieser. Je tiefer eingerückt, desto weiter innen liegt der Aufruf.
hanoi(3, links→rechts)
├─ hanoi(2, links→Mitte)
│ ├─ hanoi(1, links→rechts) … 1 nach rechts
│ ├─ 2 in die Mitte
│ └─ hanoi(1, rechts→Mitte) … 1 in die Mitte
├─ 3 nach rechts
└─ hanoi(2, Mitte→rechts)
├─ hanoi(1, Mitte→links) … 1 nach links
├─ 2 nach rechts
└─ hanoi(1, links→rechts) … 1 nach rechts Die Folge der „Bewegungen“, von oben nach unten gelesen, ist genau die Lösung mit 7 Zügen. Ein Aufruf erzeugt in sich zwei weitere Aufrufe, deshalb verdoppelt sich die Arbeit ungefähr mit jeder zusätzlichen Scheibe.
Aufwand
| Was untersucht wird | Bei n Scheiben |
|---|---|
| Zahl der Bewegungen (Züge) | 2ⁿ − 1 |
| Zahl der Aufrufe von hanoi (Aufrufe mit 0 Scheiben mitgezählt) | 2ⁿ⁺¹ − 1 |
| Tiefe der Aufrufe (wie viel man gleichzeitig behalten muss) | n + 1 Ebenen |
Warum die Zahl der Züge 2ⁿ − 1 beträgt, beweist die Formel für die Mindestzahl der Züge. Die Zeit wächst exponentiell mit der Scheibenzahl (O(2ⁿ)), während das, was man sich merken muss, nur proportional zur Scheibenzahl wächst (O(n)). Weil es allein schon 2ⁿ − 1 Züge gibt, dauert es, so geschickt man es auch anstellt, mindestens so lange, die ganze Zugfolge aufzuschreiben.
Lösen ohne Rekursion
Man kann es auch ohne Rekursion nur mit einer Schleife lösen. Das ist genau das Verfahren für das Lösen von Hand aus dem Artikel zur Lösungsmethode.
Prozedur hanoi_loop(n):
Richtung von Scheibe 1 festlegen (n ungerade: links→rechts→Mitte, n gerade: links→Mitte→rechts)
für Zug = 1, 2, 3, … , 2ⁿ − 1 wiederholen:
ist Zug ungerade, Scheibe 1 in der festgelegten Richtung zum nächsten Stab bewegen
ist Zug gerade, die obersten Scheiben der zwei Stäbe ohne Scheibe 1 vergleichen
und die kleinere auf die größere (oder auf einen leeren Stab) bewegen Anders als bei der Rekursion muss man sich keine Aufrufe merken, also braucht man sehr wenig Speicher.
Jeden Zug direkt aus dem Binärsystem berechnen
Es gibt sogar eine Möglichkeit, für jeden Zug direkt auszurechnen, was zu tun ist, ohne die Züge davor durchzugehen. Nummeriere die Stäbe mit 0, 1 und 2. Für Zug m (von 1 an gezählt) gilt:
- Bewegt wird die Scheibe mit der Nummer Anzahl der Nullen am Ende von m im Binärsystem + 1.
- Der Stab, von dem bewegt wird, ist der Rest von (m AND (m − 1)) geteilt durch 3.
- Der Stab, auf den bewegt wird, ist der Rest von ((m OR (m − 1)) + 1) geteilt durch 3.
AND und OR sind die stellenweisen Rechnungen „und“ und „oder“ im Binärsystem. Bei m = 4 (im Binärsystem 100) gibt es zum Beispiel 2 Nullen am Ende, also ist es Scheibe 3. Der Ausgangsstab ist (4 AND 3) = 0, also Stab 0, und der Zielstab ergibt sich aus ((4 OR 3) + 1) = 8, der Rest von 8 geteilt durch 3 ist 2, also Stab 2.
Die Züge nach dieser Formel führen bei einer ungeraden Scheibenzahl von Stab 0 auf Stab 2 und bei einer geraden Scheibenzahl von Stab 0 auf Stab 1. Will man bei gerader Scheibenzahl auf Stab 2 bewegen, liest man Stab 1 und Stab 2 vertauscht. Wie Zugzahl und Binärsystem zusammenhängen, steht ausführlicher im Artikel zu den Regelmäßigkeiten.
