import mathe.FormattedOut;
/**
* AlgDs WS99 Aufgabe 33.
* Tuerme von Hanoi
*
* @author Christian Semrau, 26.12.1999
*
* Christian.Semrau@student.uni-magdeburg.de
*/
class ChS_Aufg33 {
int anzahl; // die gesamte Anzahl der Scheiben
int[][] stab; // die Scheiben auf den Staeben
int[] stabtop; // die Anzahl der Scheiben auf den Staeben
/**
* Legt neue "Tuerme von Hanoi" an. Die Anzahl der Scheiben wird als Parameter
* uebergeben. Stab 0 wird mit den Scheiben gefuellt, die beiden anderen Staebe
* (1 und 2) sind leer.
*/
public ChS_Aufg33(int anz) {
anzahl = anz;
stab = new int[3][anz]; stab[0] = init(anz);
stabtop = new int[3]; stabtop[0] = anz;
}
/** Liefert ein int-Feld, das absteigend mit den Zahlen anzahl bis 1 gefuellt ist. */
public static int[] init(int anzahl) {
int[] a = new int[anzahl];
for (int i=0; istab[S2][l2-1]))
// tauschen: statt von S1 nach S2 jetzt von S2 nach S1 verschieben
{int h = S1; S1 = S2; S2 = h;}
versetzeObersten(S1,S2); output("von "+S1+" nach "+S2+":");
}
/** Versetzt die oberste Scheibe von Quelle
nach Ziel
. */
public void versetzeObersten(int Quelle, int Ziel) {
stab[Ziel][stabtop[Ziel]++] = stab[Quelle][--stabtop[Quelle]];
}
/**
* Verlagert iterativ hoehe
Scheiben von Stab
* Quelle
nach Stab Ziel
.
*
* @param hoehe die Hoehe des zu bewegenden Turmes
* (dh wieviele Scheiben bewegt werden sollen)
* @param Quelle von welchem Stab
* @param Hilfe auf welchen Stab wird ausgelagert
* @param Ziel auf welchen Stab
*/
public void versetzeTurmIterativ(int hoehe, int Quelle, int Hilfe, int Ziel) {
if (hoehe <= 0) return; // sicher ist sicher
int[] next = new int[3];
if (hoehe % 2 == 0){
// kleinste Scheibe wandert von Quelle nach Hilfe nach Ziel nach Quelle
next[Quelle] = Hilfe; next[Hilfe] = Ziel; next[Ziel] = Quelle;
}else{
// kleinste Scheibe wandert von Quelle nach Ziel nach Hilfe nach Quelle
next[Quelle] = Ziel; next[Hilfe] = Quelle; next[Ziel] = Hilfe;
}
int aktQ = Quelle, aktH = Hilfe, aktZ = Ziel, schritte = (1 << hoehe) - 1;
System.out.println(schritte+" Schritte.");
while (schritte > 0) {
if (schritte % 2 == 1) {
int nextQ = next[aktQ];
versetzeObersten(aktQ, nextQ);
output("Obersten von "+aktQ+" nach "+nextQ+":");
aktQ = nextQ; aktH = next[aktH]; aktZ = next[aktZ];
}else{
versetzeMoeglich(aktH, aktZ);
}
schritte--;
}
}
/**
* Verlagert rekursiv hoehe
Scheiben von Stab
* Quelle
nach Stab Ziel
.
*
* @param hoehe die Hoehe des zu bewegenden Turmes
* (dh wieviele Scheiben bewegt werden sollen)
* @param Quelle von welchem Stab
* @param Hilfe auf welchen Stab wird ausgelagert
* @param Ziel auf welchen Stab
*/
public void versetzeTurmRekursiv(int hoehe, int Quelle, int Hilfe, int Ziel) {
if (hoehe <= 0) return; // man weiss ja nie
if (hoehe > 1) versetzeTurmRekursiv(hoehe-1, Quelle, Ziel, Hilfe);
versetzeObersten(Quelle, Ziel);
output("Obersten von "+Quelle+" nach "+Ziel+":");
if (hoehe > 1) versetzeTurmRekursiv(hoehe-1, Hilfe, Quelle, Ziel);
}
} // ChS_Aufg33