Türme von Hanoi
Türme von Hanoi ist ein mathematisches Knobel- und Geduldsspiel.
Es besteht aus drei Feldern, auf die Scheiben verschiedener Größe gelegt werden können. Zu Beginn sind alle Scheiben auf einem Feld, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Bei jedem Zug darf die oberste Scheibe eines beliebigen Feldes auf eines der beiden anderen Felder gelegt werden, vorausgesetzt, dort liegt nicht schon eine kleinere Scheibe. Ziel des Spiel ist es, den kompletten Scheiben-Stapel auf ein anderes Feld zu versetzen.
Vermutlich wurde das Spiel 1883 vom französischen Mathematiker Edouard Lucas erfunden. Er dachte sich dazu die Geschichte aus, dass indische Mönche einen Turm aus 64 Scheiben versetzen müssten, und wenn ihnen das gelungen sei, wäre das Ende der Welt gekommen.
Obwohl es auf den ersten Blick kompliziert klingt, gibt es für das Spiel einen ganz einfachen rekursiven Algorithmus. Da sich ein Computerprogramm zur Lösung des Spiels mit wenigen Zeilen schreiben lässt, ist Türme von Hanoi ein klassisches Beispiel für rekursive Programmierung.
Die minimale Anzahl von Zügen für einen Stapel aus n Scheiben beträgt 2n-1, bei einem Turm von 8 Scheiben (die gängigste Variante) also 255 Züge. Für den Stapel aus 64 Scheiben würden 18.446.744.073.709.551.615, also mehr als 18 Trillionen Züge benötigt. Würde man jede Sekunde eine Scheibe bewegen, bräuchte man dafür etwa 580 Milliarden Jahre.