Türme von Hanoi

23.04.2015, 07:07

Björn

Türme von Hanoi

Meine Frage:
Hi Leute,

ich hätte eine Frage zu den Türmen von Hanoi. Den Code habe ich bereits, allerdings erscheinen mir einige Sachen nicht ganz logisch. Erstmal der Code:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

package hanoi;
import java.util.Scanner; 
public class Hanoi 
{
    public static void main(String[] args) 
    {
        int n;
        Scanner read = new Scanner (System.in); 
        System.out.println("Wie viele Scheiben?");
        n = read.nextInt(); 
        
        hanoi(n,'A','B','C');
    }

    static void hanoi (int n, char x, char y, char z)
    {
        if (n==1)
        {
            System.out.println("Scheibe "+n+" von " +x+ " nach " + y);
        }
        else
        {
            hanoi(n-1,x,z,y);
            System.out.println("Scheibe "+n+" von " +x+ " nach " + y);
            hanoi (n-1,z,y,x);
        }
    }
}

Meine Ideen:
Meine Frage jetzt: Wie genau läuft die Rekursion im else-Zweig ab?

Vielen Dank

23.04.2015, 16:00

Auf diesen Beitrag antworten »

eulerscheZahl

Das Programm arbeitet so:
Wir haben einen Turm aus mehreren Scheiben, die alle auf Stapel x liegen.
Alle bis auf die unterste (des aktuellen Teilstapels, der nicht dem Gesamtstapel entsprechen muss) werden nach z geschoben. Dadurch ist auf y Platz für die unterste Scheibe. Die restlichen können dann von z, wo sie zwischengeparkt wurden, auch nach x.

23.04.2015, 19:58

Auf diesen Beitrag antworten »

Björn

Danke für die Antwort. Allerdings leuchtet mir die Rekursion immer noch nicht ganz ein. Könntest du mir das vielleicht Schritt für Schritt erklären? (2 oder 3 Scheiben vollkommen ausreichend, sonst sind es ewig viele Schritte)

23.04.2015, 22:26

Auf diesen Beitrag antworten »

eulerscheZahl

Aufgrund meiner Faulheit unvollendet. Ich hoffe, man kann es trotzdem verstehen.

Graue Felder sind fest und in der aktuellen Rekursionstiefe nicht berücksichtigt, weiß ist leer.

25.04.2015, 19:25

Auf diesen Beitrag antworten »

Björn

Vielen Dank :-)

12.11.2015, 21:52

Auf diesen Beitrag antworten »

Tina_92

Ich klinke mich hier einmal in dieses Problem ein, da ich es nicht ganz verstehe: Annahme, dass n=3, x=A, y=B und z = C

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

static void hanoi (int n, char x, char y, char z)
    {
        if (n==1)
        {
            System.out.println("Scheibe "+n+" von " +x+ " nach " + y);
        }
        else
        {
            hanoi(n-1,x,z,y);
            System.out.println("Scheibe "+n+" von " +x+ " nach " + y);
            hanoi (n-1,z,y,x);
        }
    }

Wie sehe ich den Ablauf:

n = 3;
Erste if-Abfrage wird geprüft --> false, also springt der Compiler in den else-Zweig. Hier heißt die rekursive Funktion jetzt:

code:
1:	hanoi(2,x,z,y)

Dann startet der Aufruf wieder von vorne, n ist ungleich eins, somit wieder in den else - Zwei. Der Aufruf lautet:

code:
1:	hanoi(1,x,z,y)

Jetzt ist n==1, somit erfolgt die Ausgabe
Scheibe 1 von A nach B und die Funktion hanoi schließt sich, also lautet die nächste Ausgabe
Scheibe 2 von ...........

Nur weiß ich absolut nicht, wie sich meine chars x,y und z während des rekursiven Aufrufes verhalten. Das mit n ist mir klar, nur nicht die Buchstaben.

Vielen Dank für jegliche Antwort :-)

12.11.2015, 22:21

Auf diesen Beitrag antworten »

eulerscheZahl

Die Buchstaben 'A', 'B', 'C' sind in der aufgerufenen Unterfunktion entsprechend vertauscht. In der aufrufenden Funktion ändert sich dadurch aber nichts.
Besorge dir am besten eine Entwicklungsumgebung (eclipse oder NetBeans), falls noch nicht geschehen. Da kannst du den Code zeilenweise durchlaufen und die Variablen beobachten.

Im Bild:
oben links die Aufrufliste der Funktionen, wenn du da eine Zeile anklickst, aktualisiert sich der Inhalt der Variablen (oben rechts) für den Zustand. Im Code unten kannst du Haltepunkte setzen.

12.11.2015, 22:29

Auf diesen Beitrag antworten »

Tina_92

Danke für die schnelle Antwort. Wie kann ich denn den Code in NetBeans einzeln durchlaufen?

12.11.2015, 22:36

Auf diesen Beitrag antworten »

eulerscheZahl

1. rechts auf die Zeilennummer klicken (Breakpoint setzen)
2. Programm im Debug Modus starten (Strg + F5 oder Icon rechts von normalen Ausführen)
3. Es sollten jetzt neue Icons in der Menüleiste erscheinen (Continue, Step into, ...), damit kannst du schrittweise weitergehen.

12.11.2015, 22:42

Auf diesen Beitrag antworten »

Tina_92

Vielen Dank :-)

Neue Frage »

Antworten »

Türme von Hanoi

Verwandte Themen