G
Guest
Gast
Hallo, ich habe einen interessanten Code zu den Türmen von Hanoi gefunden, nur leider verstehe ich ihn noch nicht ganz:
Die Implementierung der Stange:
Implementierung der Scheibe
und Hanoi mit Algorithmus
Also dort läuft ja ein rekursiver Algorithmus ab, dass nur verschoben wird, wenn größter und kleinster identisch sind:
Mein generelles problem ist:
kleinster ist doch immer 1, oder?
Wie kann es dann sein , dass dann die scheiben 2 und 3 verschoben werden und nicht nur die kleinste und die größte:
weil generell wird doch nur verschoben, wenn kleinster und größter identisch sind
Die Implementierung der Stange:
Code:
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
/** Diese Klasse repraesentiert eine Stange, auf
* der einzelne Scheiben aufgereiht werden koennen.
**/
public class Stange {
/** Die einzelnen Scheiben werden in einer Liste
* abgelegt.
**/
private List<Scheibe> scheiben = new ArrayList<Scheibe>();
/** Fuegt der Stange genau dann eine einzelne Scheibe
* hinzu, wenn nicht schon eine kleinere Scheibe auf
* der Stange sitzt.
* @param scheibe die hinzugefuegte Scheibe
* @return true, wenn das Einfuegen erfolgreich war
**/
public boolean fuegeEin(Scheibe scheibe) {
// Test: haben wir versucht, null einzufuegen?
if (scheibe == null)
return false;
// Test: ist die Stange leer?
if (!scheiben.isEmpty()) {
// Hole die oberste Scheibe aus der Liste
Scheibe oben = (Scheibe) scheiben.get(0);
// Vergleiche die Breiten der Scheiben
if (oben.getBreite() < scheibe.getBreite())
return false;
}
// Fuehre die Operation durch
scheiben.add(0,scheibe);
return true;
}
/** Entfernt das oberste Element vom Turm.
* @return das oberste Element, null, falls
* die Stange leer ist.
**/
public Scheibe entferne() {
if (scheiben.isEmpty()) {
return null;
}
return (Scheibe)scheiben.remove(0);
}
/** Gib die Hoehe des Turms aus
* @return die Anzahl der Scheiben, die auf der Stange
* aufgereiht sind.
**/
public int getHoehe() {
return scheiben.size();
}
/** Gibt eine String-Repraesentation des Objektes zurueck.
* @return eine textuelle Darstellung der Stange
**/
public String toString() {
// Wir speichern das Ergebnis in einem StringBuffer zwischen
StringBuffer res = new StringBuffer("||=");
// ... und iterieren durch die Liste
for (Iterator it = scheiben.iterator(); it.hasNext(); ) {
res.insert(2,it.next()); // impliziter Aufruf von toString()
res.insert(2,'=');
}
// Fertig :-)
return res.toString();
}
}Implementierung der Scheibe
Code:
import java.text.DecimalFormat;
/** Diese Klasse repraesentiert eine einzelne Scheibe,
* die waehrend des Tuerme-von-Hanoi-Spieles hin- und
* hergeschoben wird.
**/
public class Scheibe {
/** Formatierungs-Objekt fuer die Breite */
private final static DecimalFormat FORMAT = new DecimalFormat("00");
/** Wie breit ist die Scheibe ? */
private int breite;
/** Konstruktor.
* @param breite die Breite der Scheibe.
**/
public Scheibe(int breite) {
this.breite = breite;
}
/** Liefert die Breite der Scheibe zurueck
* @return die Breite der Scheibe
**/
public int getBreite() {
return breite;
}
/** Gibt eine String-Repraesentation des Objektes zurueck.
* @return eine textuelle Darstellung der Stange
**/
public String toString() {
return "(" + FORMAT.format(breite) + ")";
}
}und Hanoi mit Algorithmus
Code:
/** Dieses Programm loest das Tuerme-von-Hanoi-Problem
* und gibt die Loesung auf dem Bildschirm aus.
**/
public class Hanoi {
/** Ein Zaehler fuer die Zuege */
private int zaehler;
/** Die drei Tuerme */
private Stange[] stangen = {
new Stange(),new Stange(),new Stange()
};
/** Konstruktor
* @param anzahl die Anzahl der Scheiben
**/
public Hanoi(int anzahl) {
for (int i = anzahl; i > 0; i--)
stangen[0].fuegeEin(new Scheibe(i));
}
/** Liefert eine String-Darstellung des
* aktuellen Zustandes.
* @return die drei Stangen in textueller Darstellung
**/
public String toString() {
StringBuffer res = new StringBuffer();
res.append("Start: ");
res.append(stangen[0].toString());
res.append('\n');
res.append("Ziel: ");
res.append(stangen[1].toString());
res.append('\n');
res.append("Hilfsstange: ");
res.append(stangen[2].toString());
return res.toString();
}
/** main-Methode: Erhaelt die Anzahl der Scheiben als
* Kommandozeilenparameter und startet den Algorithmus.
**/
public static void main(String[] args) {
if (args.length != 1) {
System.out.println("Korrekter Aufruf: Hanoi <Anzahl Scheiben>");
return;
}
int anzahl = Integer.parseInt(args[0]);
new Hanoi(anzahl).spiele();
}
/** Der eigentliche (rekursive) Verschiebe-Algorithmus.
* @param kleinste die kleinste zu verschiebende Scheibe
* @param groesste die groesste zu verschiebende Scheibe
* @param start index der Stange, von der wir starten
* @param ziel index der Stange, auf die wir schieben
*/
private void rekursion(int kleinste,int groesste,int start,int ziel){
// Falls kleinste == groesste ist, sind wir am Ende der
// Rekursion (und koennen direkt verschieben)
if ( kleinste == groesste ) {
// Die eigentliche Verschiebung
boolean ok = stangen[ziel].fuegeEin(stangen[start].entferne());
assert ok;
// Gib den Zustand der Tuerme aus
System.out.println("Zug : " + (++zaehler));
System.out.println(this);
System.out.println();
}
// Andernfalls muessen wir etwas mehr tun
else {
// Schiebe die kleineren Scheiben auf einen anderen Turm
rekursion(kleinste, groesste - 1, start, 3 - start - ziel);
// Dann verschiebe die groesste Scheibe
rekursion(groesste,groesste,start,ziel);
// Danach schiebe die ganzen kleineren ebenfalls aufs Ziel
rekursion(kleinste, groesste - 1, 3 - start - ziel, ziel);
}
}
/** Fuehre den "Tuerme von Hanoi"-Algorithmus durch */
public void spiele() {
if (zaehler > 0)
return;
System.out.println("Ausgangszustand:");
System.out.println(this);
System.out.println();
rekursion(1,stangen[0].getHoehe(),0,1);
}
}Also dort läuft ja ein rekursiver Algorithmus ab, dass nur verschoben wird, wenn größter und kleinster identisch sind:
Mein generelles problem ist:
kleinster ist doch immer 1, oder?
Wie kann es dann sein , dass dann die scheiben 2 und 3 verschoben werden und nicht nur die kleinste und die größte:
weil generell wird doch nur verschoben, wenn kleinster und größter identisch sind
