Hanoi

[kulturfenster]

Hallo allerseits,
Ich versuche gerade, das Problem der Türme von Hanoi rekursiv zu lösen. Leider stecke ich schon ziemlich am Anfang fest. Natürlich könnte ich schnell danach googlen, doch der lerneffekt wäre dann gleich null. Wäre also froh, wenn mir jemand Tipps geben könnte, wie ich's anpacken muss.

Hier mein Versuch:

static void hanoi(int n, int from, int to) 
{
    if(n>1) hanoi(n-1, from, 3-to-from);
    System.out.println(from + " -> " + to);
...
}

Tipps?
Vielen Dank!

 

[solnze]

ich habs an der FH gehasst und bis heute nicht wirklich kapiert.

wer da als quasi anfaenger selber drauf kommt vor dem zieh ich den hut.
(also die rekursive loesung in quasi 3-4 zeilen )

denke diese aufgabe wird gestellt damit sich die leute damit beschaeftigen wenn einer ne loesung am naechsten tag praesentiert weiss der prof wenigst dass derjenige gut im internet surfen kann.

 

[kulturfenster]

oh, danke für die Antwort!

In meinem Fall wurde die Aufgabe am Anfang einer Vorlesung gestellt und das Resultat gegen Ende erwartet. Googeln sei in unserem eigenen Interesse verboten.
Zu meinem Unbehagen haben sich einige meiner Mitstudenten aber wesentlich weniger schwer mit der Aufgabe herumgeschlagen...

 

[kleiner_held]

formal beschrieben:
1. wie man eine Scheibe von A nach B transferiert brauche ich wohl nicht zu beschreiben
2. zwei Scheiben von A nach B heißt
- die erste Scheibe von A nach C zu packen
- dann die Zweite Scheibe von A nach B
- zuletzt die erste auch wieder von C nach B
3. drei Scheiben von A nach B:
- 2 Scheiben von A nach C packen
- die dritte Scheibe von A nach B
- 2 Scheiben von C nach B
...
PS: ich hoffe der Tip war dir jetzt nicht schon zu umfangreich

 

[kulturfenster]

wie das "Spiel" funktioniert hab ich begriffen. Hier noch ein applet dazu: http://jeans.studentenweb.org/study/hanoi/hanoi.html

das Problem ist mehr die Rekursion dabei.
Intuitiv würde ich das Problem mit ArrayListen lösen, was aber nicht die Aufgabe ist.

Trotzdem Danke für die Antwort!

 

[kleiner_held]

Naja dann müsstest du doch die Lösung eigentlich schon haben oder?
Wenn man X Scheiben von A nach B schieben will, muss man
1. X - 1 von A nach C
2. genau eine von A nach B
3. X - 1 von C nach B
transferieren.

Das "genau eine" kann man direkt machen, für X-1 benötigt man Rekursion.

 

[Marco13]

Zu meinem Unbehagen haben sich einige meiner Mitstudenten aber wesentlich weniger schwer mit der Aufgabe herumgeschlagen...

Geh davon aus, dass sie die Lösung schon kannten :roll: (und nachher ist sie ja soooo einfach.... :wink: )

 

[kulturfenster]

also zurück zur Rekursion:

angenommen, ich spiele mit 3 Scheiben, so werden folgende Methoden aufgerufen: (bitte korrigieren, falls falsch)

1. hanoi(3,0,2);
2. da n > 1: hanoi(2,0,1);
3. hanoi(1,0,2)

Soweit so gut. Ich habe nun lediglich Zahlen eingesetzt. Wegen dem Verständnis... ???:L
Verstehe ich das richtig, dass n lediglich zu Beginn eine klare Bedeutung (Anz Scheiben) hat??
Des weitern verstehe ich der 3. Aufruf von der hanoi-methode nicht. hanoi(1,0,2) bedeutet meines erachtens, dass sich 1 Scheibe auf A befindet und diese nach C verschoben wird. Dies ist ja auch das Ziel, nur befindet sich dort leider noch die 1. Scheibe (wegen 1. Aufruf).

Liegt der Fehler am Programm oder in meinem Kopf? :?

hmm, auch mit 2 Scheiben werde ich nicht schlau:

hanoi(2,0,2) ist ja eh schon falsch, da man bei lediglich 2 Scheiben die erste Scheibe auf B verschieben sollte.

......Bahnhof-Alarm.........


kennt sich jemand damit aus??

 

[SlaterB]

> Verstehe ich das richtig, dass n lediglich zu Beginn eine klare Bedeutung (Anz Scheiben) hat??

worauf beziehst du dich? auf die zwei Zeilen Code vom Anfang?
n hat in jedem Programm der Welt genau die Bedeutung, die man ihm zuweist..
wenn das Programm von dir ist, dann legst DU die Bedeutung fest

> Des weitern verstehe ich der 3. Aufruf von der hanoi-methode nicht.

ich auch nicht, was bedeuten die drei Zahlen?
ist das wieder aus deinem Programm?
dann musst du das doch erklären..

worauf beziehst du dich???

 

[SlaterB]

-- doppelt, warum auch immer --

 

[kulturfenster]

ich beziehe mich paar Zeilen Code am Anfang des Threads. Leider stammen diese nicht von mir, sondern stellen lediglich den Anfang einer Übunsaufgabe dar, in der es darum geht, das Problem der "Türme von Hanoi" rekursiv zu programmieren.

doppelt??

 

[Marco13]

Naja. Diese Methodenaufrufe sind so eben nicht ganz eindeutlig.

Du hast drei Säulen. Auf Säule 0 liegen 3 Scheiben. Und diese 3 Scheiben willst du von Säule 0 auf Säule 2 bewegen. Dazu mußt du

2 Scheiben von 0 nach 1 (damit die unterste, größte Scheibe frei liegt)
1 Scheibe (die größte) von 0 nach 2 (da kommen nachher die 2 Scheiben drauf, die jetzt noch auf 1 liegen)
2 Scheiben von 1 nach 2 (auf die größte Scheibe, die ja jetzt schon auf Säule 2 liegt)

Bei Rekursionen ist es im allgemeinen sinnvoll, zuerst den "Basisfall" abzufragen. Der "Basisfall" ist hier der Fall, wo man nur EINE Scheibe bewegen muss. Also

Bewege N Scheiben von A nach B
{
    Wenn (nur noch eine scheibe übrig ist)
    {
        Bewege die scheibe von A nach B
    }
    Andernfalls
    {
        Nimm erstmal alle Scheiben bis auf eine (die größte) von A runter, und lege sie auf C
        Bewege die Größte Scheibe von A nach B
        Bewege die Scheiben, die auf C liegen, nach B
    }
}

Die Signatur der Methode könnte sein

hanoi(int anzahlScheiben, int startSäule, int zielSäule, int zwischenlagerSäule)

 

[kulturfenster]

Vielen Dank für die hilfreiche Antwort!

Trotzdem ist leider einiges noch unklar.

Ich habe versucht, die Methode ohne die Varible "ZwischenlagerSäule" zu schreiben, wie es die Aufgabenstellung vorschreibt.

public class Hanoi {

	public void hanoi(int anzScheiben, int startSäule, int zielSäule)
	{
	      if(anzScheiben == 1) hanoi(1,0,2);
	      else hanoi((anzScheiben - 1), 0,1);
	      if(anzScheiben == 0) hanoi(0,1,2); // Falls A leer ist, alle Scheiben von B nach C (Endlager) verschieben.
	      System.out.println(zielSäule);
	}
	
	public static void main(String[] args)
	{
		Hanoi h = new Hanoi();
		
		h.hanoi(3,0,2);
	}
}

Gibt leider einen StackoverFlow. Wo hab ich Mist gebaut?

 

[SlaterB]

dazu brauchst du nichtmal denken, dass Programm sagt dir, was es tut..

public void hanoi(int anzScheiben, int startSäule, int zielSäule) 
   { 
        System.out.println("Autruf hanoi, anzScheiben: "+anzScheiben)

         if(anzScheiben == 1) { 
             System.out.println("anzScheiben == 1, rufe nun Hanoi auf");
             hanoi(1,0,2); 
         }
         else  { 
             System.out.println("anzScheiben != 1, rufe nun Hanoi auf");

             hanoi((anzScheiben - 1), 0,1); 
         }
         if(anzScheiben == 0)  {
                System.out.println("anzScheiben == 0, rufe nun Hanoi auf");
               hanoi(0,1,2); 
               // Falls A leer ist, alle Scheiben von B nach C (Endlager) verschieben. 
         }
         System.out.println(zielSäule); 
   }

 

[Leroy42]

formal beschrieben:
1. wie man eine Scheibe von A nach B transferiert brauche ich wohl nicht zu beschreiben
2. zwei Scheiben von A nach B heißt
- die erste Scheibe von A nach C zu packen
- dann die Zweite Scheibe von A nach B
- zuletzt die erste auch wieder von C nach B
3. drei Scheiben von A nach B:
- 2 Scheiben von A nach C packen
- die dritte Scheibe von A nach B
- 2 Scheiben von C nach B
...

Genau das ist der falsche Ansatz rekursiv zu denken! :noe:

Besser:

Du mußt einen Turm von n Stangen von Stange-A nach Stange-B transportieren

1. Transportiere n-1 Stangen von Stange-A nach Stange-C
2. Transportiere 1 Stange von Stange-A nach Stange-B
3. Transportiere n-1 Stangen von Stange-C nach Stange-B

Hierbei ist nur zu beachten, daß n, Stange-A, Stange-B und Stange-C
keine fixen Werte, sondern Platzhalter sind

==> Schon hast du den entsprechenden Java (C, ...) Code!

 

[Marco13]

Die "festen" Argumente
hanoi(1,0,2);
machen auch keinen Sinn. Die Säulen nehmen je unterschiedliche Rollen ein (und die "Zwischenlager-Säule" kannst du aus den anderen beiden ausrechnen - und es ist wichtig, dass sie RICHTIG ausgerechnet wird)

Überleg' dir das mal an einem richtigen "Trace". Wenn du drei Säulen A, B und C hast, und nun 3 Scheiben von A nach C bewegen willst, dann machst du folgendes:

Bewege 3 Scheiben von A nach C, mit B als Zwischenalger
{
    Bewege 2 Scheiben von A nach B, mit C als Zwischenalger
    {
         Bewege 1 Scheiben von A nach C
         Bewege 1 Scheiben von A nach B
         Bewege 1 Scheiben von C nach B
    }

    Bewege 1 Scheiben von A nach B

    Bewege 2 Scheiben von B nach C, mit A als Zwischenalger
    {
         Bewege 1 Scheiben von B nach A
         Bewege 1 Scheiben von B nach C
         Bewege 1 Scheiben von A nach C
    }
}

 

[Marco13]

@Leroy42: Das ist nicht der falsche Ansatz, es ist nur eine "iterative" Beschreibung dessen, was bei der Rekursion abläuft. Das, was du geschrieben hast, wurde schon in ähnlicher Form gesagt, aber es hat (offenbar) nicht zum Verständnis beigetragen....

 

[Leroy42]

@Leroy42: Das ist nicht der falsche Ansatz, es ist nur eine "iterative" Beschreibung dessen, was bei der Rekursion abläuft.

Genau das meinte ich ja.

Zu versuchen, eine iterative Beschreibung auszudenken, könnte
einen den Wald vor lauter Bäumen nicht mehr sehen lassen.

Laß dir dies von jemanden sagen, der frühzeitig mit dem Buch

Knödel-Esser Bach(*)

aufgewachsen ist!


(*) oder so ähnlich... ???:L

 

[kleiner_held]

Wieso falcher Ansatz? Es war nach Hinweisen fuer eine Rekursion gesucht, nicht nach einer fertigen Loesung.
Wenn man zuerst den Fall N=1 beschreibt und beim Fall N=2 auf (N=1) verweist, dann ist da der Hinweis fuer den Ansatz einer Rekursion enthalten. Ob das nun unverstaendlicher ist als eine Erklaerung: Betrachte N=X als Erweiterung von N=X-1 und lasse den Spezialfall N=1 nicht aus den Augen sei mal dahingestellt.

PS: bin aber nicht mit Knödel-Esser Bach aufgewachsen sondern mit BASIC

 

[kulturfenster]

==> Schon hast du den entsprechenden Java (C, ...) Code! icon_biggrin.gif

So einfach scheints leider nicht zu sein. Trotzdem danke für die Platzhalter - Anmerkung!

Ich habe nun den SOF behoben, bin mir aber nicht sicher, ob es nun nicht zu simpel ist. Die einzelnen Schritte (Scheibenverschiebungen) sind jedenfalls nicht erkennbar.

Kann man das so machen? Oder ist es zu simpel?

public void hanoi(int anzScheiben, int startSäule, int zielSäule)
	   {
	         if(anzScheiben == 2) {
	             System.out.println("0 -> 2");

	             hanoi((anzScheiben - 1), 0,2);
	         }
	         if(anzScheiben > 2)  {
	             System.out.println("0 -> 1");

	             hanoi((anzScheiben - 1), 0,1);
	         }
	         if(anzScheiben == 1)  {
	                System.out.println("1 -> 2");
	                hanoi((anzScheiben - 1), 1,2);
	               // Falls A leer ist, alle Scheiben von B nach C (Endlager) verschieben.
	         }
	         System.out.println(zielSäule);
	         
	    }

Noch eine allgemeine Frage zu Rekursion: Die Ausgabe des Programms, beinhaltet die Verschiebungen der Scheiben und 4 mal die zielSäule. Ich dachte, wenn die Methode rekursiv aufgerufen wird, geschieht dies sogleich, ohne dass noch die ganze Methode durchgerackert wird.

Ich dachte,

 if(anzScheiben > 2)  {
	             System.out.println("0 -> 1");

	             hanoi((anzScheiben - 1), 0,1);
	         }

beendet die Methode und ruft sie neu auf, SOFERN anzScheiben >2!? Wieso wird dann noch die letzte Anweisung "System.out.println(zielSäule);" ausgeführt?

 

[Leroy42]

PS: bin aber nicht mit Knödel-Esser Bach aufgewachsen sondern mit BASIC

Ach so! Das erklärt natürlich alles. :shock:

Dir sei verziehen!

:toll:

 

[Leroy42]

Kann man das so machen? Oder ist es zu simpel?

Es ist eher zu kompliziert!

beendet die Methode und ruft sie neu auf, SOFERN anzScheiben >2!?

Nein! Die Methode wird hier noch nicht beendet, sondern zuerst wird die
Methode erneut(rekursiv) aufgerufen, währen der aktuelle Aufruf in seinem
Zustand verharrt/suspendiert wird.

Nach Beendigung des rekursiven Aufrufs, wird dann der aktuelle Aufruf
zu Ende ausgeführt; also das System.out.println(zielSäule); noch aufgerufen.

 

[Leroy42]

Ich glaube, du hast dich jetzt genug damit beschäftigt um eine fertige Lösung
nachvollziehen zu können:

public void hanoi(int anzScheiben, int startSäule, int zielSäule, int hilfsSäule) {
  if (anzScheiben == 0)
    return;

  hanoi(anzScheiben-1, startSäule, hilfsSäule, zielSäule);
  System.out.printf("Scheibe %d von Stange %d nach Stange %d.%n", anzScheiben, startSäule, zielSäule);
  hanoi(anzScheiben-1, hilfsSäule, zielSäule, startSäule);
}

 

[kulturfenster]

ok, danke für die Erklärung!

nun meine (hoffentlich) letzte Frage: Ist das die Lösung des Problems, dh zu meiner ersten Frage? Ich frage deshalb, weil die Ausgabe stimmt, wenn sie auch stark vereinfacht ist. Dh, über jegliches Umstapeln wird hinweggesehen.

1. Alle Scheiben befinden sich auf A
2. n-1 Scheiben nach B
3. verbleibende Scheibe von A nach C
4. Scheiben von B nach C

public void hanoi(int anzScheiben, int startSäule, int zielSäule)
	   {
	         
	         if(anzScheiben > 1)  {
	             System.out.println("0 -> 1");

	             hanoi((anzScheiben - 1), 0,1);
	         }
	         
	         if(anzScheiben == 1)  {
	                System.out.println("0 -> 2");
	                hanoi((anzScheiben - 1), 1,2);
	               // Falls A leer ist, alle Scheiben von B nach C (Endlager) verschieben.
	         }
	         
	         if(anzScheiben == 0) {
	        	 System.out.println("1 -> 2");
	        	 
	         }
	         System.out.println(zielSäule);
	         
	    }

 

[Leroy42]

Bei Rekursionen ist es im allgemeinen sinnvoll, zuerst den "Basisfall" abzufragen. Der "Basisfall" ist hier der Fall, wo man nur EINE Scheibe bewegen muss.

:noe:

Für mich ist der Basisfall der, bei der gar keine Scheibe bewegt werden muß. ( )

Das heißt für mich, das du in der Schule zu denjenigen gehört hast, die
bei Induktionsbeweisen immer n=1 statt n=0 als Induktionsanfang
genommen haben ==> Selber schuld!

Summe(i=1, n, i) = 1/2 * n * (n+1)

Induktionsanfang: n = 0

==>

Summe(i=1, 0, i) = 0 = 1/2 * 0 * (0+1)

ist doch wesentlich weniger zu rechnen.

 

[kulturfenster]

okok, danke, das hät bestimmt noch Jahre gedauert.

Ich versuch die mickrigen 2 Zeilen mal zu verstehen...

Kannst du mir aber schnell deine Schreibweise von

System.out.printf("Scheibe %d von Stange %d nach Stange %d.%n", anzScheiben, startSäule, zielSäule);

erklären?

%d, %n ??

 

[Leroy42]

okok, danke, das hät bestimmt noch Jahre gedauert.

Ich versuch die mickrigen 2 Zeilen mal zu verstehen...

Kannst du mir aber schnell deine Schreibweise von

System.out.printf("Scheibe %d von Stange %d nach Stange %d.%n", anzScheiben, startSäule, zielSäule);

erklären?

%d, %n ??

Das ist das seit Java 1.5 eingeführte, in C von Anfang an bekannte, formatted printing

Die %ds sind Platzhalter für die nachfolgenden Integer; die werden an deren
Stellen eingesetzt.

 

[Marco13]

Etwas pragmatisch formuliert würde ich sagen: Der Basisfall ist der, den man abfragt.

Du würdest ja nicht schreiben

hanoi(int n, ...)
{
    if (n==0) return;
    else ...
}

weil dadurch ungefähr 2^n sinnlose Methodenaufrufe gemacht werden, sondern (wenn überhaupt) dann

hanoi(int n, ...)
{
    if (n>1) hanoi(n-1...);
    move(...);
    if (n>1) hanoi(n-1...);
}

und dann kann man (der Einfachheit und Übersichtlichkeit halber) gleich schreiben

hanoi(int n, ...)
{
    if (n==1) move(...);
    else ... // rekursion
}

... irgendwie, irgendwo, irgendwann muss die Abfrage gemacht werden :roll: Es ging um die allgemeine Struktur rekursiver Funktionen, ähnlich der definition von primitiver Rekursion http://de.wikipedia.org/wiki/Primitiv-rekursive_Funktion

Und ob die nun bei 0 oder bei 1 anfängt ist (für die Sache an sich) ziemlich egal...

 

[Leroy42]

Und ob die nun bei 0 oder bei 1 anfängt ist (für die Sache an sich) ziemlich egal...

Hast volkommen recht!

Nur, ich persönlich, nehme lieber 2^n zusätzliche leere Methodenaufrufe
in Kauf wenn ich dadurch eine mathematischere und vollständigere Lösung erreiche.

public void hanoi(int n, int a, int b, int c) {
  if (n>0) {
    hanoi(n-1, a, c, b);
    move(n, a, b);
    hanoi(n-1, c, b, a);
  }
}

finde ich halt ästhetischer.

Aber das ist Geschmackssache.