Türme von Hanoi, Fortsetzung

Als du in der vorangegangenen Übung die Türme von Hanoi für drei Scheiben gelöst hast, musstest du die unterste Scheibe Nummer 3 freilegen um sie von Stift A nach Stift B zu bewegen. Um Scheibe 3 freizulegen musstest du die Scheiben 1 und 2 von Stift A auf den freien Stift C bewegen:

Moment mal - es sieht so aus, als ob sich zwei Scheiben in einem Schritt bewegen und damit die erste Regel verletzen. Aber sie haben sich nicht in einem Schritt bewegt. Du hast zugestimmt, dass du die Scheiben 1 und 2 in drei Schritten von einem beliebigen Stift zu einem beliebigen Stift bewegen kannst. Die obige Situation stellt dar, was du nach drei Schritten hast. (Verschiebe Scheibe 1 von Stift A nach Stift B; verschiebe Scheibe 2 von Stift A nach Stift C; verschiebe Scheibe 1 von Stift B nach Stift C.)

Indem man die Scheiben 1 und 2 von Stift A zu Stift C bewegt, löst man rekursiv ein Unterproblem: Bewege Scheiben 1 bis $n-1$‍ (in unserem Fall ist $n=3$‍) von Stift A to nach C. Sobald du dieses Unterproblem gelöst hast kannst du die Scheibe 3 von Stift A nach Stift B bewegen:

Abschliessend musst du noch das Unterproblem rekursiv lösen, das darin besteht die Scheiben 1 bis $n-1$‍ vom Stift C nach B zu bewegen. Wir wissen bereits, dass das in drei Schritten erledigt werden kann (Bewege Scheibe 1 von Stift C auf Stift A; bewege Scheibe 2 von C nach B; bewege Scheibe 1 von Stift A auf Stift B.) Geschafft:

Und – du ahnst sicher, dass diese Frage kommen musste – macht es etwas aus von und zu welchen Stiften du die Scheiben 1 bis 3 bewegst? Du hättest sie von und auf beliebige Stifte ziehen können. Zum Beispiel von Stift B auf Stift C:

Ganz gleich wie man es dreht und wendet, du kannst die Scheiben 1 bis 3 von jedem Stift auf jeden anderen Stift mit 7 Zügen bewegen. Zweimal, wenn die Scheiben 1 und 2 bewegt werden, fallen jeweils drei Züge an, plus ein Zug für das einmalige Bewegen der Scheibe 3.

Was ist, wenn $n=4$‍? Weil wir bereits wissen wie das Unterproblem, bestehend aus drei Scheiben gelöst werden kann, können wir auch das Problem für $n=4$‍ lösen.

Insgesamt werden für diese Lösung 15 Züge benötigt (7 + 1 + 7). Auch dies gilt allgemein für jeden beliebigen Start- und Zielstift.

Du siehst vielleicht schon zwei Muster auftauchen. Erstens kann man die Türme von Hanoi rekursiv lösen. Wenn $n=1$‍, dann bewege einfach Scheibe 1. Ansonsten, wenn $n\ge 2$‍, löse das Problem in drei Schritten:

Zweitens, das Lösen eines Problems für $n$‍ Scheiben erfordert $2^n-1$‍ Züge. Wir haben gesehen, dass das wahr ist wenn:

Wenn du ein Problem für $n-1$‍ Scheiben in $2^{n-1}-1$‍ Zügen lösen kannst, dann kannst du ein Problem für $n$‍ Scheiben in $2^n-1$‍ Zügen lösen. Du brauchst:

Wenn du die Züge addierst, erhältst du $2^n-1$‍.

Zurück zu den Mönchen. Sie benutzen $n=64$‍ Scheiben, und so müssen sie eine Scheibe $2^{64}-1$‍ mal bewegen. Diese Mönche sind flink und stark. Sie können jede Sekunde eine Scheibe bewegen, Tag und Nacht.

Wie lang ist $2^{64}-1$‍ Sekunden? Wenn man die grobe Schätzung von 365,25 Tagen pro Jahr verwendet, sind das 584.542.046.090,6263 Jahre. Das sind 584+ Milliarden Jahre. Die Sonne hat nur noch etwa fünf bis sieben Milliarden Jahre übrig, bevor sie zur Supernova wird. Also, ja, die Welt wird untergehen, aber egal wie hartnäckig die Mönche auch sein mögen, es wird lange vorher passieren, bevor sie alle 64 Scheiben auf Stift B bringen können.

Wenn du wissen willst wozu dieser Algorithmus sonst noch verwendet werden kann, ausser das Ende der Welt vorauszusagen, dann schau' mal auf Wikipedia nach. Dort findest du einige interessante Anwendungen.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.