Aus Das deutschsprachige Scratch-Wiki

Die Türme von Hanoi ist ein von dem französischen Mathematiker Edouard Lucas 1883 erfundenes mathematisches Problem und Geduldspiel.

In Hanoi, der Hauptstadt von Vietnam, stehen in einem Tempel drei Säulen. Auf einer dieser Säulen liegen 64 Scheiben, deren Durchmesser, von oben nach unten gesehen, immer größer wird. Das heißt, es liegt immer eine kleinere auf einer größeren Scheibe. Die Aufgabe der Mönche in diesem Tempel ist es, die 64 Scheiben auf eine andere Säule zu stapeln. Dabei dürfen sie eine dritte Säule zu Hilfe nehmen, denn niemals darf eine größere auf eine kleinere Scheibe gelegt werden. Man sagt, wenn die Mönche ihre Aufgabe erfüllt haben werden, wird die Welt untergehen...

Wann wird das sein? Nun, wir müssen uns keine Sorgen machen. Angenommen, die Mönche benötigen für das Umlegen einer Scheibe 10 Sekunden, dann werden sie in ca. 5849424173550 Jahren fertig sein. Das ist um Vieles mehr als das gesamte Universum alt ist.

Wie viele Umlegevorgänge benötigt man allgemein für n Scheiben?

Bei einer Scheibe ist man schnell fertig: Einfach in einem Zug auf die Ziel-Säule umlegen.

Bei zwei Scheiben benötigt man schon die Hilfs-Säule. Die kleine, oben liegen Scheibe wird auf die Hilfs-Säule gelegt, die größere wird auf die Ziel-Säule gelegt und die kleine kommt oben darauf. Man benötigt also 3 Züge.

Wäre die kleinere Scheibe ein ganzer Turm gewesen, etwa aus zwei Scheiben bestehend, dann hätte man zuerst diese zwei Scheiben auf die Hilfssäule bringen müssen (dies benötigt, wie gerade gezeigt, 3 Züge), dann die größere Scheibe umlegen und dann die zwei kleineren wieder mit 3 Zügen darauf legen müssen. Das ergibt in Summe 7 Züge, die sich aus 3+1+3 zusammensetzen. Man benötigt also immer für n Scheiben die Zuganzahl für n-1 Scheiben + 1 + die Zuganzahl für n-1 Scheiben, denn die größte Scheibe am Ende benötigt nur einen Zug, daher ziehen wir von den n Scheiben eine ab und gleichen das wieder dadurch aus, dass wir den einen Zug, der für das Umlegen der Scheibe benötigt wird, hinzuaddieren (+ 1).

Das Problem lässt sich also rekursiv formulieren, das heißt, es lässt sich auf das nächstkleinere Problem (mit einer Scheibe weniger) zurückführen. Zuganzahl(n) = Zuganzahl(n-1)+1+Zuganzahl(n-1) = 2*Zuganzahl(n-1)+1 (Wobei natürlich die Zuganzahl(0) = 0 ist.)

Da man für eine Scheibe einen Zug, für 2 Scheiben 3 Züge und für 3 Scheiben 7 Züge benötigt, liegt der Verdacht nahe, dass man allgemein für n Scheiben 2n - 1 Züge benötigt. Setzt man das in die zuvor gefundene Formel Zuganzahl(n) = 2*Zuganzahl(n-1) + 1 ein, so bekommt man 2n - 1 = 2*(2n-1 - 1) + 1 = 2n - 2 + 1 = 2n - 1, also eine wahre Aussage.

Die Zuganzahl wächst also exponentiell. Dies erklärt den ungeheuer großen Wert für n=64. Eine einfach formulierte Aufgabenstellung kann also eine Komplexität entwickeln, die jeden Rahmen (auch bezüglich Berechenbarkeit am Computer) sprengt.

Die folgende Funktion realisiert das Umlegen gemäß der rekursiven Definition:

Definiere bewege (Scheibenanzahl) (SäuleA) (SäuleB) (SäuleC)
falls <<(Scheibenanzahl) > [0]>> dann
bewege ((Scheibenanzahl) - (1)) (SäuleA) (SäuleC) (SäuleB) //alle Scheiben bis auf die größte auf den Hilfsstapel bringen
sage (verbinde (verbinde (verbinde [Lege die oberste Scheibe von Säule ] [SäuleA]) [ auf Säule ]) [SäuleC]) für (2) Sek. //eine Scheibe umlegen (im aktuellen Kontext ist das immer die größte...)
bewege ((Scheibenanzahl) - (1)) (SäuleB) (SäuleA) (SäuleC) //alle Scheiben bis auf die größte auf die umgelegte, größte Scheibe legen
ende

Beispiele

821691_144x108.png

Tower of Hanoi sehr langsam ablaufend

260752_144x108.png

Tower of Hanoi Ein schnelleres Programm mit Darstellung der genutzten Listen und Variablen


Weiterführende Informationen

  • Wikipedia-Artikel "Türme von Hanoi" [1]



Code zum Einbinden ins Forum:
[wiki=de:Türme von Hanoi]Türme von Hanoi[/wiki]