Türme von Hanoi
www.infos-aus-germanien.info
Einordnung: Geduldsspiel
- Was heißt Türme von Hanoi auf:
Englisch - Französisch - Italienisch - Niederländisch und Schwedisch sowie Spanisch
- Sie wissen mehr über das Thema Türme von Hanoi und möchten uns dazu etwas mitteilen?
Benutzen Sie dazu bitte unser Forum und eröffnen Sie einen neuen Thread zum Thema Türme von Hanoi.
Die Türme von Hanoi sind ein mathematisches Knobel- und Geduldsspiel.
| Inhaltsverzeichnis |
Aufbau
Das Spiel 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.
| | |
= | |
=== | |
===== | |
======= | |
========= | |
=========== | |
--------------- --------------- ---------------
Startfeld Zielfeld
Geschichte
Vermutlich wurde das Spiel 1883 vom französischen Mathematiker Edouard Lucas erfunden. Er dachte sich dazu die Geschichte aus, dass indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, einen Turm aus 64 goldenen Scheiben versetzen müssten, und wenn ihnen das gelungen sei, wäre das Ende der Welt gekommen.
Lösungsalgorithmus
right
Man kann Türme von Hanoi mit verschiedenen Anzahlen von Scheiben spielen. Das Lösungsprinzip ändert sich dadurch nicht. Der einfachste nicht völlig triviale Fall ist der mit 3 Scheiben. Wenn man versteht, wie man 3 Scheiben von einem Stab (Turm) zum anderen bewegt, kann man damit auch jeden Fall mit beliebiger Anzahl von Scheiben lösen. Lösung des 3-Scheiben-Falles: Nennen wir die 3 Stäbe (Türme) von links nach rechts A,B,C und die Scheiben von klein nach groß 1,2,3, dann gibt ein Zahl-Buchstabenpaar an welche Scheibe wohin bewegt werden soll (3B bedeutet z.B. die größte der 3 Scheiben soll auf den mittleren Turm gelegt werden).
Hier sind die Lösungsschritte: 1C,2B,1B,3C,1A,2C,1C (7 Schritte)
Es ist zu beachten, dass die erste Scheibe dorthin bewegt wird, wo sich letztendlich die drei Scheiben befinden sollen. Um jetzt mit diesem Lösungsalgorithmus das Problem mit 4 Scheiben zu lösen, bewegt man die drei Scheiben auf den Turm, der nicht das Ziel ist (hier also B), bewegt dann die Scheibe 4 auf den Zielstab, um danach die drei Scheiben von B nach C zu bewegen.
Hier sind die Lösungsschritte: 1B,2C,1C,3B,1A,2B,1B,4C,1C,2A,1A,3C,1B,2C,1C (15 Schritte)
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 über 584 Milliarden Jahre.
Beispiel-Algorithmus (geschrieben in der Programmiersprache Scheme):
n = Anzahl der Scheiben
(define hanoi
(lambda (n aktuell ziel)
(begin (cond ((> n 1) (hanoi (- n 1) aktuell (- (- 6 aktuell) ziel))))
(display
(string-append "Setze Scheibe " (number->string n)
" von Platz " (number->string aktuell)
" nach Platz " (number->string ziel) ". "))
(cond ((> n 1) (hanoi (- n 1) (- (- 6 aktuell) ziel) ziel))))))
Aufruf: > (hanoi n 1 2)
Weblinks
- weitere Weblinks
- Hanoi Tutorialit illustrierter Anwendung zur Erstellung von Lösungen und kommentiertem Algorithmus
- mister-mueller Anschauliche Darstellung mit einer ausführlichen Erklärung.
- hanoimania Implementation in 110 verschiedenen Programmiersprachen.
- Suche nach Türme von Hanoi Infos mit: Yahoo