Jetzt traue ich mich auch mal hier zu posten!
Gab es das schon? In den FAQ’s habe ich es nicht gefunden.
http://www.sachsen-freizeit.de/games/hanoi/hanoi.html
Grüße
Frank
Jetzt traue ich mich auch mal hier zu posten!
Gab es das schon? In den FAQ’s habe ich es nicht gefunden.
http://www.sachsen-freizeit.de/games/hanoi/hanoi.html
Grüße
Frank
Nicht das ich wüsste. Aber - wer dazu ne Lösung haben möchte, ich hab mal über diese Problematik nachgedacht und erstaunliche Ergebnisse erhalten.
Habe schon VBA-Programme geschrieben, mit denen ich einmal die kompletten Züge bis zu einer bestimmten Zahl anzeigen lassen kann (lfd. Nr, „Ring“-Nummer und „von - nach“[Ich glaub bei ca. 30 Ringen hat das Programm abgebrochen, da die txt-Datei mit über 500MB voll war]) oder auch herausfinden kann, wie die Ringe an einer bestimmten Stelle stehen (zb bei 1023 Ringen der 104.567te Zug).
Jedenfalls ist es ganz einfach zu lösen.
Gruß Tobias
Hi!
Jedenfalls ist es ganz einfach zu lösen.
Stimmt!
Start:
Alle Scheiben befinden sich auf Position A
Die linke Hand greift sich die kleinste Scheibe (und lässt sie bis zum Ende des Spieles nicht mehr los).
2.
Die Scheibe in der linken Hand wandert jetzt auf den nächsten Zapfen (von Position A auf Position B). Die linke Hand hält die Scheibe dort fest.
3.
Die rechte Hand nimmt die kleinste freie Scheibe und bringt sie auf die einzige verfügbare Möglichkeit (hier von Position A auf Position C) und gibt die Scheibe frei
4.
Die Scheibe, die von der linken Hand gehalten wird, wandert jetzt von Position B nach Position C (und wird weiter von der linken Hand festgehalten)
5.
Die rechte Hand nimmt die kleinste freie Scheibe und bringt sie auf die einzige verfügbare Möglichkeit (hier von Position A auf Position B) und gibt die Scheibe frei
6.
Die Scheibe, die von der linken Hand gehalten wird, wandert jetzt von Position C nach Position A (und wird weiter von der linken Hand festgehalten)
7.
Die rechte Hand nimmt die kleinste freie Scheibe und bringt sie auf die einzige verfügbare Möglichkeit (hier von Position C auf Position B und gibt die Scheibe frei)
8.
Die Scheibe in der linken Hand wandert jetzt auf den nächsten Zapfen (von Position A auf Position B). Die linke Hand hält die Scheibe dort fest.
usw. usw.
Das Schema ist damit klar: die kleinste Scheibe wandert immer von A nach B nach C nach A und wird in jedem zweiten Zug bewegt. Damit ergibt sich für die anderen Scheiben eine Zwangsreihenfolge.
Ob die kleinste Scheibe den Weg A - B - C - A oder A - C - B - A einschlägt, ist abhängig, wo der Turm am Spielende stehen soll (neuer Turm auf B oder C) und ob die Anzahl der Scheiben geradzahlig oder ungeradzahlig ist. Das Prinzip ist immer das gleiche - und es wird immer die Mindestzugzahl erreicht.
Grüße
Heinrich
ja, also ich fands auch nicht so schwer
Der Haken ist jedoch, daß dieses Problem in O(d^n) liegt. Daher die Schwierigkeit steig extreee(so viele „e“'s kann ich hier garnicht schreiben!)eeem schnell mit steigender ‚Stufenanzahl‘ an.
Die ursprünglichen Türme hatten afaik 64 Stufen. Ein Mönchsorden war der festen Überzeugung, daß die Welt unterginge an dem Tag, an dem diese Aufgabe gelöst ist.
Darauf können wir aber noch lange warten… mit 64 Scheiben und einem Zug pro 5 Sekunden rund um die Uhr würde das wohl etwa drei Billion Jahre dauern.
Hi,
Einfach war es, mich hat es ein wenig an Solitär erinnert.
MfG, Alex
Ist ein Standardproblem für Programmierer, um sog. rekursive Prozeduren/Funktionen zu begreifen. Dazu stellt man sich für Scheiben, die von Pin A nach Pin B unter Zuhilfenahme von Pin C bewegt werden sollen, folgendes vor:
Man bewegt alle außer der untersten Scheibe von Pin A nach Pin C
2.
Man nimmt die größte Scheibe und setzt sie auf Pin B
3.
Man nimmt alle Scheiben (aus 1.) und setzt sie von Pin C auf Pin B
Die Schritte 1 und 3 lassen sich wieder in die gleichen 3 Schritte unterteilen, diesmal aber mit einer Scheibe weniger, und jeweils mit anderen Pins (weil die Scheiben ja schon mal umgesetzt wurden).
Das kann man dann immer weiter treiben. Also in dem jeweils kleiner gemachten Problem werden immer wieder Schritt 1 und Schritt 3 durch das gleiche Verfahren (Schritt 1, 2, 3) ersetzen, bis das Problem sich auf eine Scheibe reduziert hat.
Ein Programm ‚Bewege_Scheiben‘, das eine bestimmte Anzahl Scheiben von ‚VollerPin‘ nach ‚ErsterLeererPin‘ (unter Zuhilfenahme von ‚ZweiterLeererPin‘) verschieben soll, sieht in etwa so aus.
PROGRAMM Bewege\_Scheiben (AnzahlScheiben,
VollerPin,
ErsterLeererPin,
ZweiterLeererPin)
SELBSTAUFRUF: Bewege\_Scheiben (AnzahlScheiben - 1,
VollerPin,
ZweiterLeererPin,
ErsterLeererPin)
AUSGABE ("Scheibe von 'VollerPin' nach 'ErsterLeererPin' verschieben")
SELBSTAUFRUF: Bewege\_Scheiben (AnzahlScheiben - 1,
ZweiterLeererPin,
ErsterLeererPin,
VollerPin)
ENDE
Wenn ich dieses Programm mit
Bewege\_Scheiben (10, A, B, C)
starte, macht es folgendes:
1. AUFRUF: Bewege\_Scheiben (9, A, C, B)
2. AUSGABE ("Scheibe von A nach B verschieben")
3. AUFRUF: Bewege\_Scheiben (9, C, B, A)
was bedeutet:
- Bewege 9 Scheiben von A nach C (mit Hilfe von B)
- „Scheibe von A nach B verschieben“
- Bewege 9 Scheiben von C nach B (mit Hilfe von A)
Das Programm ruft sich selbst also mit 9 Scheiben, die von einem Pin zu einem anderen bewegt werden müssen, auf. Und das 9-Scheiben-Problem führt zu einem 8-Scheiben-Problem, u.s.w.
Das Programm rugft sich also mit einer immer kleiner werdenden Anzahl Scheiben auf und dröselt so das große Problem auf. (Was hier noch fehlen würde, ist eine Abfrage, ob ‚Anzahl_Scheiben‘ durch das ständige „-1“ schon Null geworden ist, aber das hab ich hier mal weggelassen.)
Ist für Nicht-EDV-ler etwas schwierig, weil in jedem neuen Selbstaufruf die gleichen Bezeichnungen (z.B. VollerPin, ZweiterLeererPin) auftauchen, diese aber in jedem Aufruf immer andere Pins bezeichnen. Und ja, dass das funktioniert, ist manchmal selbst für Informatiker, die es zum ersten mal sehen, sehr verblüffend.
Gruß
Wolfgang
Jetzt traue ich mich auch mal hier zu posten!
Gab es das schon? In den FAQ’s habe ich es nicht gefunden.
http://www.sachsen-freizeit.de/games/hanoi/hanoi.html
Grüße
Frank