Rekursiver Algorithmus: Türme von Hanoi

[Timo Trallala]

Tach Zusammen,

wahrscheinlich kann es keiner mehr hören und es gibt bestimmt auch interessantere Probleme als meines: Das mit den Rekursionen hab ich schon verstanden, aber mit folgendem listing kommich nicht ganz klar, will heißen, was passiert hier im einzelnen und vor allem was soll die Zeile nach dem println:

public class ToH {
  static void Tow (String Quelle, String Hilf, String Ziel, int n) {
    if (n ==1) 
      System.out.println ("Bewege Scheibe " +n+ " von " + Quelle + " nach " + Ziel);
    else {
      Tow (Quelle, Ziel, Hilf, n-1);
      System.out.println ("Bewege Scheibe " +n+ " von " + Quelle + " nach " + Ziel);
      Tow (Hilf, Quelle, Ziel, n-1);
    }
  }

  public static void main (String args []) {
    System.out.println ("Tuerme von Hanoi");
    Tow ("Quelle", "Hilfsziel", "Ziel", 3);
  }
}

Wäre echt ne feine Sache, wenn mir da mal jemand auf die Sprünge helfen könnte!

Grüße aus Duisburg

Timo :###

 

[Bleiglanz]

ist doch klar
n=3 die anzahl der scheiben
"quelle","ziel","hilfsziel" sind die 3 Stapel

wenn n=1,
========
dann gibt er einfach aus, dass er die Quelle zum Ziel schieben soll (das ist ja wohl klar)

wenn n>1, dann
============
Löst er das Problem mit (n-1) Steinen (aber mit Ziel und Hilfsziel vertauscht, d.h. er schiebt n-1 auf das Hilfsziel)

dann System.out.println: er legt die Scheibe n einfach von der Quelle zum Ziel

dann Löst er das Problem mit (n-1) (aber jetzt vom Hilfziel ausgehend auf Ziel mit quelle als hilfsziel), d.h. er legt jetzt die n-1 wieder aufs ziel

ist nur schlecht formuliert wegen den Strings

 

[Timo Trallala]

THX a Lot :toll:

 

[stev.glasow]

:lol:
War das mal 'n Boxer oder hat er beim Volleyball nicht auf gepasst ?

 

[merc]

Hallo,

wollte für mein Anliegen keinen neuen Thread aufmachen. Ich denke, das reicht auch so...

Ich bin derzeit auch an den "Türmen" drauf und dran, aber mit vier statt drei Stangen. Es klappt nur nicht. Anscheinend versteh ich die Rekursion doch nicht, wie ich erst zu Anfang dachte. Weiß jemand eine Lösung oder hat einen Tipp für mich?

Gruß
merc

 

[Leroy42]

aber mit vier statt drei Stangen

Wie soll das denn gehen :shock:
Die 4. Stange ist schlichtweg überflüssig.

Nun kann es vielleicht sein, daß bei Verwendung von 4 Stangen weniger Schritte
benötigt werden aber dann kommt mit Sicherheit ein völlig anderer Algorithmus
zum Tragen dein ein fähiger Mathematiker erst mal auf die Beine stellen muß.

Hast du dir die Aufgabe selbst gestellt, wurde sie dir gestellt oder hast du davon
irgendwo gelesen? In den letzten beiden Fällen wird dort bestimmt der Algorithmus
vorgegeben, den du posten kannst um dir zu helfen zu implementieren.

Im ersten Fall wünsche ich dir viel Spaß

 

[merc]

hi,

die aufgabe wurde mir mit dem hinweis gestellt, dass dies eine kleine modifikation darstellen würde. hier ein kleines, mathematisches beispiel: www.mathematische-basteleien.de/hanoi.htm

ich habe bis jetzt versucht, die problematik sowohl logisch als auch nach dem prinzip try-and-error zu behandeln. aber scheint nicht so trivial zu sein, wie ich dachte. wenn jemand ne idee hätte, wäre ich sehr dankbar.

gruß,
merc

 

[Leroy42]

Genau was ich vermutete: Man braucht weniger Züge.
Aber ich kann mir nicht vorstellen, wie man so ad hoc einen rekursiven Algorithmus
aus der Nase schüttelt, der dies leistet. Ich denke es ist komplizierter als die, eher
naheliegende, 3-Stangen Lösung.

Mich würde diese Aufgabe zwar auch reizen, habe aber im Moment keine Zeit dazu.

Versuch doch einfach mal das für einige Anzahl Scheiben selbst auszuprobieren.
- erst ab 3 Scheiben zeigt sich ein Unterschied - und versuche daraus eine
Regelmäßigkeit abzulesen. So kommst du bestimmt am schnellsten auf den
Algorithmus. Den mußt du dann nur noch in Java coden.

 

[Leroy42]

Ich habe mal ein Programm zum Erkunden des Problems ins Netz gestellt, und,
weil es micht auch interessiert, gleich einen neuen Thread aufgemacht.

Guckst du hier