Die Türme von Hanoi

Letztmalig dran rumgefummelt: 09.12.07 15:20:08

	Auf der Pariser Weltausstellung von 1889 hatte der französische Zahlentheoretiker Édouard Lucas (1842 - 1891), Lehrer am Lycée St. Louis zu Paris, etliche seiner kombinatorischen Spiele ausgestellt, darunter auch das Turmspiel. Dieses Spiel war von Lucas um 1883 erfunden und unter dem Pseudonym N. Claus de Siam (=Lucas d'Amiens) auf den Markt gebracht worden. Um es interessanter zu machen, hatte er folgende phantastische Geschichte ausgedacht: Im großen Tempel zu Benares, der den Mittelpunkt der Welt bezeichnet, stehen drei diamantene Säulen. Auf eine davon hat der Herr zu Beginn der Zeiten 64 goldene Scheiben gesteckt; dieser Turm ist Brahma geweiht. Tag und Nacht sind die Tempelpriester damit beschäftigt, den Turm nach folgenden Regeln umzubauen: Die Scheiben dürfen nur einzeln umgesetzt, eine Scheibe darf nie auf eine kleinere gelegt, und zum Umbau des Turmes dürfen alle drei Säulen benutzt werden. Wenn das Werk vollendet, d. h. der Turm von der ersten auf die zweite Säule umgesetzt ist, zerfallen Turm und Priester zu Staub, und das Ende der Welt ist gekommen.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für die Türme von Hanoi Basiswissen der Informatik Wissen für Fortgeschrittene der Informatik Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	der "Worst-Case" liegt hier sicher nicht in der Komplexität zum Aufwand für den Lösungsalgorithmus - er ist hier allein in der Mächtigkeit des Problems zu suchen
	die Anzahl der Zwischenwerte, die zur Lösung für ein Argument benötigt werden ist schlichtweg enorm und steigt mit n-polynomial
	Das sind die Türme von Hanoi für Dich zum Probieren Das sind die Türme von Hanoi für Dich im .CDR 11-Format Das ist die Variante für unsere Mitstreiter, die in absehbarer Zeit fertig werden wollen Das sind die Türme von Hanoi für Dich im .CDR 11-Format
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer
	Knobelaufgaben, welche sich auf das Prinzip der Türme von Hanoi zurückführen lassen :-)

1. Problembeschreibung

	Nach einer Überlieferung waren buddhistische Mönche mit einer Aufgabe beschäftigt, die ein außerordentliches Maß an Geduld erfordert: Auf einem Brett stehen drei Pfähle, aus Kupfer, Silber und Gold. Irgendwann vor langer Zeit staken auf dem Kupferstab 100 Lochscheiben, alle mit verschiedenen Durchmessern und der Größe nach geordnet. (vergl. Abb.) Die Aufgabe ist nun, den Stapel auf den goldenen Pfahl umzuschichten. Mit den heutigen Kenntnissen über Algorithmen weiß man, dass dies ein rekursives Problem ist. Wenn bekannt ist, wie man einen Turm von 99 Scheiben umsetzen kann, ist es auch möglich, einen Turm aus 100 Scheiben umzusetzen. Doch um einen Turm aus 99 Scheiben umzusetzen, sollte bekannt sein, wie man das mit einem Turm aus 98 Scheiben macht. usw... Überlegt man sich diese Verfahren für wenige Scheiben erkennt man, dass bei n Scheiben insgesamt 2n-1 Schritte notwendig sind. Bei 5 Scheiben wären das 31 Schritte. Dies ist machbar und eine schöne Denkaufgabe. Jedoch bei 100 Scheiben ergeben sich rund 126.765.060.000.000.000.000.000.000.000 Schritte. Selbst der schnellste Mönch (1 Sekunde je Zug) wäre nicht in der Lage dies zu schaffen, denn dann müsste er 40.000.000.000.000.000.000.000 (40 Trilliarden) Jahre arbeiten. Das würde wirklich den Weltuntergang bedeuten.

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Der Lösungsalgorithmus für die Türme von Hanoi
	effiziente Lösung nur als rekursiver Algorithmus
	n-polynomialer Aufwand

3. Lösungsalgorithmus

	Setze immer die nächst kleinere Scheibe auf eine Position, so dass die sie dann umgebenden Untergrundfläche immer noch den Umriss der Untergrundscheibe erkennen lässt (also immer eine kleiner auf eine größere Scheibe).
	Ausgangssituation Ausgangssituation 1. Schritt graue Scheibe auf Position 3 2. Schritt blaue Scheibe auf Position 2 3. Schritt graue Scheibe auf Position 2 4. Schritt graue Scheibe auf Position 2 5. Schritt graue Scheibe auf Position 1 6. Schritt blaue Scheibe auf Position 3 7. Schritt graue Scheibe auf Position 3 8. Schritt grüne Scheibe auf Position 2 9. Schritt graue Scheibe auf Position 2 10. Schritt blaue Scheibe auf Position 1 11. Schritt graue Scheibe auf Position 1 12. Schritt gelbe Scheibe auf Position 2 13. Schritt graue Scheibe auf Position 3 14. Schritt blaue Scheibe auf Position 2 15. Schritt graue Scheibe auf Position 2 16. Schritt rote Scheibe auf Position 3 17. Schritt graue Scheibe auf Position 1 18. Schritt blaue Scheibe auf Position 3 19. Schritt graue Scheibe auf Position 3 20. Schritt gelbe Scheibe auf Position 1 21. Schritt graue Scheibe auf Position 2 22. Schritt graue Scheibe auf Position 2 23. Schritt blaue Scheibe auf Position 1 24. Schritt graue Scheibe auf Position 1 25. Schritt grüne Scheibe auf Position 3 26. Schritt graue Scheibe auf Position 3 27. Schritt blaue Scheibe auf Position 2 28. Schritt graue Scheibe auf Position 2 29. Schritt gelbe Scheibe auf Position 3 30. Schritt graue Scheibe auf Position 1 31. Schritt blaue Scheibe auf Position 3 32. Schritt graue Scheibe auf Position 3

4. Programmvorschläge

5. Zusammenfassung

	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig - er ist n-polynomial
	es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

6. Weiterführende Literatur

7. Links zum Thema

	Viele gibt es - die meisten sind JAVA-basierte Spiele, um den erkannten Lösungsalgorithmus nach zu vollziehen. Wie gesagt, wenn Du vor hast, das Spiel noch am laufenden Tag zu beenden, verwende keine Scheibenzahl größer 20 - das ist dann schon nicht mehr zu schaffen.
	http://www.blinde-kuh.de/spiele/hanoi/
	http://www.cut-the-knot.org/recurrence/hanoi.shtml

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im März 2005