Informatiker Board | Druckvorschau: Türme von Hanoi

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Türme von Hanoi (http://www.informatikerboard.de/board/thread.php?threadid=2235)

Geschrieben von Björn am 23.04.2015 um 07:07:

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

Geschrieben von eulerscheZahl am 23.04.2015 um 16:00:

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.

Geschrieben von Björn am 23.04.2015 um 19:58:

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)

Geschrieben von eulerscheZahl am 23.04.2015 um 22:26:

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.

Geschrieben von Björn am 25.04.2015 um 19:25:

Vielen Dank :-)

Geschrieben von Tina_92 am 12.11.2015 um 21:52:

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 :-)

Geschrieben von eulerscheZahl am 12.11.2015 um 22:21:

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.