Türme von Hanoi in "Java ist auch eine Insel"

[dickjustice]

Hallo liebes Forum,

ich lese gerade das Buch "Java ist auch eine Insel" und bin auf ein Verständnisproblem gestoßen.
In dem Buch wird das bekannte mathematische Problem der Türme von Hanoi geschildert. Abgesehen davon, dass ich den Code noch nicht verstehe, der im Buch steht, habe ich ein grundsätzliches Problem.

Im Text des Buches steht, dass es 3 Säulen gibt und das Ziel darin besteht, alle Scheiben von Säule 1, der Kupfersäule, auf Säule 3, die Goldsäule, zu übertragen.

Nun spricht sowohl die "an die Tempeltür genagelte" Lösung des Mönchs als auch das Code-Beispiel mit nur 4 Säulen davon, dass der endgültige Turm auf der zweiten Säule gebaut wird. Ich weiß, dass es prinzipiell keinen unterschied machen würde, dennoch stört mich, dass zwei verschiedene Sachverhalte beschrieben werden, vorallem, weil es mir so schwer fällt, das Code-Beispiel nachzuvollziehen.
Abgesehen davon verstehe ich die Lösung des Mönchs nicht so ganz, weil ich finde, dass sie uneindeutig formuliert ist. die "andere Säule" ist wahrscheinlich die zweite Säule, aber wieso nennt man sie nicht eindeutig "zweite Säule"?
Ausserdem ist das Rätsel nach dem zweiten Punkt doch bereits zu Ende, was soll der dritte Stichpunkt noch bewirken?

Ich finde das alles insich etwas widersprüchlich. Könnte mir jemand helfen?

Ich benutze die online-Version des Buchs: Galileo Computing :: Java ist auch eine Insel - 2 Imperative Sprachkonzepte

Danke schonmal für eure Hilfe

 

[minzee]

Da hast dich irgendwie verlesen. Es gibt nur 3 Säulen. Aber in deinem Beispiel gibt es 4 Scheiben. Vielleicht hast die Scheiben mit den Säulen verwechselt.

Ist egal, wie du die Säulen nennst. In meinem Buch werden sie A, B und C genannt.

 

[minzee]

Und zum Verständnis:

Es gibt die Türme A, B und C.

Aufruf der Funktion.

Auf A befinden sich n = 4 Scheiben. Diese sollen zum Turm B wandern.

Vorgehensweise:

1) n - 1 Scheiben (also 3) vom Turm A zum Turm C (ist in diesem Fall der Hilfsturm)
2) 1 Scheibe vom Turm A (die verbliebene letzte Scheibe) zum Turm B (wo letztendlich alles landen soll)
3) n - 1 Scheiben (also 3) vom Turm C zum Turm B

Erster rekursiver Schritt (zu 1)):

Auf A befinden sich n = 3 Scheiben. Diese sollen zum Turm C wandern.

Vorgehensweise:

1.1) n - 1 Scheiben (also 2) vom Turm A zum Turm B (ist in diesem Fall der Hilfsturm)
1.2) 1 Scheibe vom Turm A (die verbliebene letzte Scheibe) zum Turm C (wo in diesem rekursiven Schritt alles landen soll)
1.3) n - 1 Scheiben (also 2) vom Turm B zum Turm C

Zweiter rekursiver Schritt (zu 1.1)):

Auf A befinden sich n = 2 Scheiben. Diese sollen zum Turm B wandern.

Vorgehensweise:

1.1.1) n - 1 Scheiben (also 1) vom Turm A zum Turm C (ist in diesem Fall der Hilfsturm)
1.1.2) 1 Scheibe vom Turm A (die verbliebene letzte Scheibe) zum Turm B (wo in diesem rekursiven Schritt alles landen soll)
1.1.3) n - 1 Scheiben (also 1) vom Turm C zum Turm B

Dritter rekursiver Schritt (zu 1.1.1)):

Auf A befinden sich n = 1 Scheiben. Diese sollen zum Turm C wandern.

Vorgehensweise: Scheibe vom Turm A zum Turm C

Vierter rekursiver Schritt (zu 3)):

Auf C befinden sich n = 3 Scheiben. Diese sollen zum Turm B wandern.

Vorgehensweise:

3.1) n - 1 Scheiben (also 2) vom Turm C zum Turm A (ist in diesem Fall der Hilfsturm)
3.2) 1 Scheibe vom Turm C (die verbliebene letzte Scheibe) zum Turm B (wo in diesem rekursiven Schritt alles landen soll)
3.3) n - 1 Scheiben (also 2) vom Turm A zum Turm B

Fünfter rekursiver Schritt (zu 3.1))

....

Erkennst du das Muster?

Man spannt hier einen binären Baum auf, der mittels inorder-Variante durchlaufen wird.

                            ABC
                           /   \
            ACB                             CBA
           /   \                           /   \           
    ABC             BCA             CAB             ABC
   /   \           /   \           /   \           /   \
ACB     CBY     BAC     ACB     CBA     BAC     ACB     CBA

z. B. ABC:

A: fromPeg
B: toPeg
C: usingPeg

Bewegt man sich im Baum nach links, werden toPeg und usingPeg vertauscht. Bewegt man sich im Baum nach rechts, werden fromPeg und usingPeg vertauscht.

 

[minzee]

Ich würde den Ablauf gerne grafisch etwas schöner gestalten. Ich habe schon mal eine erste Skizze:

Anhang anzeigen 6933

Die Linie soll den Ablauf zeigen. Von oben geht es zuerst in Richtung links unten.

Aber ihr seht sicher schon das Problem. Ich bekomme das nicht auf eine Seite. Die Grafik wird leider viel zu breit. Außerdem ist das alles total unübersichtlich.

Bei den Knoten (gilt nicht für die Blätter des Baums) soll man sehen, dass sich gewisse Abläufe immer wiederholen. Darum besteht jeder Knoten aus 3 Teilen: Die oberste Grafik zeigt den Zustand vom Weg von oben nach unten. Die unterste Grafik zeigt den Zustand vom Weg von unten zu diesem Knoten. Die mittlere Grafik zeigt den Zustand, nachdem eine Scheibe ihre Position gewechselt hat.

Diese mittlere Grafik muss unbedingt bei der oberen Grafik bleiben, damit man eben diesen immerwiederkehren Ablauf erkennt.

Wie kann ich denn dieses Bild so gestalten, dass es nicht so breit und übersichtlicher wird? 🙁

 

[arilou]

Für Bildgestaltung ist das hier dann doch ein klein wenig das falsche Forum, findest du nicht?