Hanoi

[DWetzler]

Hallo, hat jemand vielleicht eine Ahnung, wo ich eine lösung für den Turm von hanoi, für 4 Türme finde. Habe schon sehr viel im netz gesucht und überall stand dass es wohl sehr viele Lösungen für den Turm von hanoi im Netz gibt, aber leider habe ich noch keine Lösung mit 4 Türmen gefunden. Suche jetzt verzweifelt nach einer rekursiven oder iterativen Lösung. Hat jemand vielleicht auch eine programmierte Lösung von Buneman( soll angeblich 1980 einen sehr einfache iterative Lösung erstellt haben) ? Im voraus Vielen Dank für eure Hilfe!

 

[Wildcard]

Du meinst wahrscheinlich diesen hier:
http://de.wikipedia.org/wiki/Die_Türme_von_Hanoi#Iterativer_Algorithmus

 

[PyroPi]

Hallo,

hab da eine Lösung für 4 Türme gefunden, allerdings in C programmiert und für 2-gefärbte Scheiben.

Viele Grüße,

PyroPi

 

[Leroy42]

Hallo!

Ich weiß nicht, ob du es warst, der dieses Thema hier vor ein paar Wochen angeschnitten
hat, aber es interessierte mich auch.

Ich habe daraufhin ein altes Java-Programm genommen, daß die Lösung für drei Stangen
anzeigt und es erlaubt die Türme vom User umzubauen und dieses erweitert.

Da ich nunmal mathematisch angehaucht bin ( ) habe ich das Programm gleich auf
N-Stangen zum Selbstbewegen erweitert. Nachdem ich ein bischen herumgespielt habe
und mir eine gewisse Systematik aufgefallen ist, habe ich einen Backtracking-Algorithmus
ermittelt der den Rechner minimale Lösungen für jede Anzahl von Stangen finden läßt.

Nachdem sich herausgestellt hatte, daß der Aufwand, bei Erhöhung der Stangenanzahl,
exponentiell anwächst (hätte ich mir ja denken können ), mußte ich noch eine
Unmenge an Baumbeschneidungen einbauen.

Wenn du willst, kann ich dir das Programm ja mal schicken; Zum Studium des Verhaltens
bei allgemeiner Anzahl von Stangen ist es sehr hilfreich (Du kannst auswählen, ob
du die Lösungsfindung mitverfolgen willst; mit einem Slider die Darstellungsgeschwindigkeit
wählen, oder die Berechnung ohne Anzeige laufen lassen und dann, Schritt für Schritt,
den Umbau beobachten).

Aber ein Hinweis:

[schild=5 fontcolor=000000 shadowcolor=C0C0C0 shieldshadow=1]Schau ja nicht zu tief in den Quelltext![/schild]

Dieses Programm entspricht nun absolut nicht meinem sonstigen Programmierstil,
aber, da es ja nur für mich ist, war mir Geschwindigkeit wichtiger als Erkenntnisse
aus Jahrzehnten Softwareengineering.

 

[Leroy42]

Du meinst wahrscheinlich diesen hier:
http://de.wikipedia.org/wiki/Die_Türme_von_Hanoi#Iterativer_Algorithmus

Der ist mir beim Herumspielen mit meinem Programm auch schon bewußt geworden.
Seitdem schaffe ich sogar einen Turm aus 8 Scheiben in 2 Minuten zu lösen

Allerdings hilft das DWetzler nicht weiter, da er eine Lösung für 4 Stangen sucht.

 

[DWetzler]

Ne, ich war das nicht der schon mal das Thema angeschnitten hatte. Aber wäre sehr nett, wenn du mir dein Programm mal schicken würdest. Glaube das mir das sehr weiterhelfen könnte! Nochmal vielen Dank für die Hilfe!

 

[Leroy42]

Hier, wie versprochen, die Programmversion, die auch optimale Lösungen für
mehr als 3 Stangen berechnet.

Hanoi.jar

Da ich das Programm nur für den Privatgebrauch geschrieben habe,
ist der Umgang nicht gerade intuitiv; darum Kurzinfo.

1. Einstellung der Anzahl Stangen/Scheiben
2. Reset drücken (setzt auch den Fokus auf's Panel für den KeyListener)
3. Die Tasten "1", "2", ... stehen für die Auswahl der Stange (von links gezählt)
4. Den Slider ganz nach unten ziehen (Maximalgeschwindigkeit)
5. Den Button "Nicht zeigen" drücken (Button ändert Label in "Zeigen")
6. Den Button "Lösen" drücken.
7. Sobald der Button nicht mehr den Text "STOP" zeigt, ist die Berechnung beenden
8. Den Button "Zeigen" drücken
9. Mit dem Mausrad nach oben scrollen um in die Startposition zu gehen.
10. Jeder "Klick" des Mausrads nach unten zeigt einen Lösungsschritt.

Hier die Sourcen; wie gesagt: Nicht zu tief reinschauen

Hanoi.zip