Die Türme von Hanoi | aus Forum Denkspiele & Rätsel

6 Antworten zu dieser Frage

Antwort von nach 4 Stunden 0 hilfreich

Re: Die Türme von Hanoi

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

Antwort von nach 13 Stunden 0 hilfreich

Re^2: Die Türme von Hanoi

Hi! Jedenfalls ist es ganz einfach zu lösen.
Stimmt!

Start:
Alle Scheiben befinden sich auf Position A

1.
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
- Antwort von nach 14 Stunden 0 hilfreich
  
  Re^3: Die Türme von Hanoi
  
  ja, also ich fands auch nicht so schwer
  - Antwort von nach 19 Stunden 0 hilfreich
    
    Re^4: Die Türme von Hanoi
    
    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.
    - Antwort von nach einem Tag 0 hilfreich
      
      Re^5: Die Türme von Hanoi
      
      Hi,
      
      Einfach war es, mich hat es ein wenig an Solitär erinnert.
      MfG, Alex

Antwort von nach 7 Tagen 1 hilfreich

Re: Die Türme von Hanoi

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:

1.
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:
1. Bewege 9 Scheiben von A nach C (mit Hilfe von B)
2. "Scheibe von A nach B verschieben"
3. 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

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!