Türme von Hanoi?
Hallo,
folgender Java Code:
Das Thema ist Rekursion und Aufgaben, bei denen eine Methode zur Berechnung der Fakultät, ... implementiert werden sollen finde ich einfach(habe das Grundprinzip der Rekursion verstanden). Der Code für die Umschichtung des Turms von A nach C wird mir aber nicht klar. Das Grundprinzip scheint ja zu sein den Turm in kleinere zu zerlegen, aber auch das wird mir irgendwie nicht klar?!
5 Antworten
Wie schiebe ich N Scheiben von A nach C? Indem ich n-1 Scheiben von A nach B schiebe, die n. nach C und nun die n-1 von B nach C.
Und wie verschiebe ich die n-1 Scheiben von A nach B? Indem ich n-2 Scheiben von A nach C verschiebe, die n-1-te nach B ..... usw. usf. . DAS ist im Endeffekt Deine Rekursion.
Wenn Du bei der Abbruchbedingugn landest, dann verschiebst Du zunächst nur die kleinste Scheibe. Dann die zweitkleinste und legst die kleinste auf, nun wandert die 3. auf die leere Stelle und die anderen beiden werden wieder über Verschiebung der kleinsten auf den Quellturm etc. in Position gebracht.
Schau Dir mal die Animation an, vielleicht erkennst Du die Rekursion optisch besser:
https://de.wikipedia.org/wiki/T%C3%BCrme_von_Hanoi#/media/Datei:Tower_of_Hanoi_4.gif
Dann kannste Dir auch gleich den Artikel anschauen, da steht eigentlich alles drin. Das mit dem Sierpinski-Dreieck ist auch interessant :-D.
Dazu musst du verstehen, wie die Türme von Hanoi funktionieren. Wenn bei A ein Turm ist, den du nach C verschieben willst, musst du zuerst alle Scheiben bis auf die unterste nach B verschieben. Dann kannst du die unterste Scheibe von A nach C bewegen, und dann die verbleibenden Scheiben von B nach C. Wenn du ein paar unterschiedlich große Scheiben (oder Objekte, die du als Scheiben verwenden kannst) hast, probier es einfach mal aus.
Sie müssen auf die mittlere Säule, damit du die unterste Scheibe auf die rechte Säule legen kannst. Um die unterste Scheibe von einer Säule auf die andere zu bewegen, müssen schließlich beide Säulen frei sein, für die restlichen Scheiben bleibt also nur eine Säule übrig.
Logisch, aber vom Algorithmus her.
Die Logik dahinter ist die Induktion!
Scheibe 1-Fall: Stelle Dir vor, Du hast eine Scheibe (ungerade Zahl) ganz links. Die schiebst Du nach ganz rechts.
Scheibe 2-Fall: Stelle Dir vor, Du hast ganz links eine große und eine kleine Scheibe (gerade Zahl). Du schiebst die ganz kleine auf die mittlere (!) und die große auf ganz hinten. Dann die ganz kleine von Mitte auf rechts (Scheibe 1-Fall von der Mittleren).
Scheibe 3-Fall: Stelle Dir vor, Du hast drei Scheiben auf einer Stange: ganz unten Groß (g), darüber Mittel (m), ganz oben Klein (k). Was machst Du? Du nimmst den Kleinen auf die hintere Stange (warum die hintere sage ich gleich bzw. weil Anzahl ungerade), das mittlere auf die mittlere Stange, dann die große auf die hintere. Jetzt hast Du zwei auf der mittleren. Es gilt also Scheibe 2-Fall von der Mittleren.
Scheibe 4-Fall: Du baust einen Scheibe 3-Fall auf der mittleren und dann gilt Scheibe 3-Fall von der Mittleren. Fängst mit klein auf mittel an (da 4 gerade)
Schiebe X-Fall: Du baust einen Scheibe (X-1)-Fall auf der Mittleren und dann gilt Scheibe (X-1)-Fall von der Mittleren. Du startest mit der mittleren Stange, wenn X gerade ist, sonst mit der hinteren Stange. Das ergibt sich unmittelbar aus Fall 1und 2.
Oder wie SevenOfNein schrieb: Es geht nur darum, die unterste Scheibe von ganz links nach ganz rechts zu schieben. Die oberen Scheiben behandele quasi als eigenen Turm, der dafür auf die Mitte zu schieben ist (ansonsten bekommt man die unterste Scheibe nicht von links nach rechts).
Ok, danke für die Antwort. Aber wie baue ich den bei N Scheiben auf der Kupfersäule(der ersten) einen Turm mit N-1 Scheiben auf dem mittleren?! Braucht man dafür nicht einen eigenen Algorithmus? Und wenn der Turm dann erst mal da steht, woher weiß ich dann wie es dann weitergeht?!
Dafür kannst du genau den gleichen Algorithmus verwenden. Du hast immer einen Stapel, wo die Scheiben liegen, einen Stapel wo die Scheiben hin sollen, und einen Stapel, den du in der Zwischenzeit als Ablage verwenden kannst.
Der Algorithmus ist ganz einfach, außer der erste Schritt, den ich aber Dir mit Fall 1 und 2 bewiesen habe:
Ist N gerade, dann geht die erste (kleinste) Scheibe auf die mittlere Stange. Ist N ungerade, geht die erste (kleinste) Scheibe nach hinten. Die zweit kleinste geht auf die jeweils andere Stange. Jetzt das kleinste auf das zweitkleinste. Wir haben also einen 2-er-Turm auf der jeweils andere Stande als der wo wie angefangen haben umzuschichten. Wir haben den ersten Schritt geschafft, nämlich einen Zweierturm auf eine andere Stange zu bewegen! (Bzw. der erste Schritt war, einen Einer-Turm auf eine andere Stange zu bewegen).
Jetzt bewegen das drittkleinste Element auf die freie Stange. Und dann den Zweier-Turm wieder auf diese umgelegte drittkleinste Scheibe. Wie man einen Zwei-Turm umlegt, wissen wir jetzt ja (siehe Abschnitt oben).
Jetzt ist wieder eine Scheibe frei. Wir legen die viertkleinste Scheibe um. Und darauf bauen wir den Dreier-Turm. Wie das geht, wissen wir, siehe Absatz oben.
Und dann ist wieder eine Stange frei und das fünstkleinste Element wird umgelegt. Wir legen darauf den Vierer-Turm, wie das geht siehe oben.
Und jetzt ist wieder eine Stange frei .. (immer dasselbe Schema, bis zur letzten Scheibe).
Damit am Ende der Turm auf der richtigen Stange steht, muss man im ersten Schritt mit der jeweiligen Stange anfangen (bei gerade N mittlere, bei ungerade die Zielstange).
So einfach ist dann doch nicht, "der gleiche Algorithmus" reicht für den Beweis der Korrektheit, aber noch nicht für die Vorgehensweise. Z.B. mit welcher Stange fängst Du an (das hängt davon ab, ob N gerade ist oder nicht).
Das erledigt die Rekursion. Wenn du Scheibe N von A nach C bewegen willst, musst du erst Scheibe N-1 von A nach B bewegen. Dazu musst du zuerst Scheibe N-2 von A nach C bewegen. Und so weiter, bis man bei der obersten Scheibe angekommen ist. Wenn du dir den abfotografierten Code anschaust, da steht nirgendwo etwas von "gerade" oder "ungerade". Das ist ja das Elegante an der Rekursion, dass man sich keine Gedanken über den exakten Ablauf keine Gedanken machen muss, sondern nur über Regelmäßigkeit, so wie bei der Induktion.
Der Knackpunkt ist immer die unterste Scheibe im Turm A. Die muss ja nach C. Deshalb muss der ganze übrige Turm in B oder A zwischengelagert werden. Bevor man die unterste Scheibe auf C legen kann. Den Code verstehe ich auch nicht, brauche sowas immer auf 22Zoll Bildschirm 😄
Wie schiebt man den Turm mit 10 Scheiben von A nach C?
Genauso wie
- 9 von A nach B
- 1 von A nach C
- 9 von B nach C
und wie 9 geht, weiß man ja von vorher :)
Danke, aber woher weiß ich: "wie 9 geht, weiß man ja von vorher"?!
9 geht so:
8 von A nach B
1 von A nach C
8 von B nach C
…
und wie 8 geht, weißt du ja :)
Wenn ich das jetzt immer weiterführe, dann bin ich ja je nach Abbruchbedingung bei 1. So wie ich das sehe, hat der Algorithmus da einen Switch zwischen toPeg und FromPeg. Wie geht es denn dann weiter?!
Nix weiter. fertig.
Wenn nur 1 Scheibe zu verschieben ist, dann ist die Aufgabe trivial.
Exakt, Lösung via Induktion oder bei Dir via Regression auf 1. Noch eine Kleinigkeit: Mit welcher Stange fängt man - mit der mittleren oder der Zielstange? Je nachdem, ob n gerade oder ungerade.
Wenn nur noch eine Scheibe zu verschieben ist, wird die ja entw. auf die mittlere oder äußere Säule gelegt. Durch die Rekursion wurde die Methode aber doch noch mit Werten > 1 aufgerufen. Woher weiß ich dann wie es weitergeht?!
Ehrlich gesagt verstehe ich diese Frage nicht ganz.
Kann es sein, dass Du die Rekursion nicht richtig verstanden hast?
Doch, divide and conquer. Teile und herrsche.
Danke. So weit ist mir das ja schon klar. Aber wie komme ich denn zunächst einmal darauf, dass der Turm N-1 auf der mittleren Säule landet?!