Hanoi rekursiv zu iterativ umbauen

[PfiffPaff]

Hallo Leute, hab mir mal hier die Hanoi-Türme rekursiv gebastelt:

public class HanoiRek {
	static void Tow(String Quelle, String Hilf, String Ziel, int n) {
		if (n == 1) 
			System.out.println ("Bewege Scheibe " +n+ " von " + Quelle + " nach " + Ziel);
		else{
			Tow(Quelle, Ziel, Hilf, n-1);
			System.out.println ("Bewege Scheibe " +n+ " von " + Quelle + " nach " + Ziel);
			Tow(Hilf, Quelle, Ziel, n-1);
		}
	}

	public static void main (String args []) {
		long start = System.currentTimeMillis();
		
		System.out.println ("Tuerme von Hanoi");
		Tow("Quelle", "Hilfsziel", "Ziel", 20);
		
		long end = System.currentTimeMillis();
		
		long duration = end - start;
		
		System.out.println("Es hat: " + duration/1000 + " Sekunden gedauert!");
	}
}

Aber das ist ja noch das einfache....
Ich würde das gerne iterativ machen und hab mir das jetzt erstmal mit Stift und Papier
überlegt.... nur irgendwie komm ich zu keinem Ergebnis da ich keine Intervalle erkennen kann.
Ich hab das mal jetzt auf dem Papier mit 6 Scheiben durchlaufen aber die Züge sind immer
anders....(Schwierig zu erklären) jedenfalls wüsste ich nicht wie ich das ordentlich in
Schleifen packen könnte damit es immer funktioniert.

 

[PfiffPaff]

public class HanoiIt {
	
	static void tow(int n) {
		int quelle = n;
		int ziel = 0;
		int hilfsziel = 0;
		
		while(quelle != 0 || hilfsziel != 0) {
			
			
		}
	}

	public static void main (String args []) {
		
	}
}

Das wäre mein Ansatz.... nur ich kann keine Regeln erstellen die IMMER
korrekt sind....

 

[Landei]

Alle möglichen iterativen Versionen: http://www.mi.hs-rm.de/~schwan/Vorlesungen/Prog1/Skripte/Prog1US9.pdf

 

[PfiffPaff]

Das habe ich auch schon gefunden, das finde ich persönlich
nur grotten schlecht. Mehr als unübersichtlich.

 

[PfiffPaff]

Hab mir jetzt mal das erarbeitet:

public class HanoiIt {
	
	static void tow(int n) {
		int[] stapel = {n, 0, 0};
		int kleinste = 0;
		int zweitKleinste = 0;
		int frei = 2;
		
		System.out.println("Quelle hat: " + stapel[0] + " Scheiben!");
		System.out.println("Ziel hat: " + stapel[1] + " Scheiben!");
		System.out.println("Hilfsziel hat: " + stapel[2] + " Scheiben!");
		
		while(stapel[0] != 0 && stapel[1] != n) {
			if(kleinste == 0) {
				stapel[0] = stapel[0]--;
				stapel[1] = stapel[1]++;
			} else if(kleinste == 1) {
				stapel[1] = stapel[1]--;
				stapel[2] = stapel[2]++;
			} else if(kleinste == 2) {
				stapel[2] = stapel[2]--;
				stapel[0] = stapel[0]++;
			}
			
			if(kleinste == 2) {
				kleinste = 0;
			} else {
				kleinste++;
			}
			
			
			if(zweitKleinste == 0 && frei == 2) {
				stapel[0] = stapel[0]--;
				stapel[2] = stapel[2]++;
			} else if(zweitKleinste == 0 && frei == 1) {
				stapel[0] = stapel[0]--;
				stapel[1] = stapel[1]++;
			} else if(zweitKleinste == 1 && frei == 0) {
				stapel[1] = stapel[1]--;
				stapel[0] = stapel[0]++;
			} else if(zweitKleinste == 1 && frei == 2) {
				stapel[1] = stapel[1]--;
				stapel[2] = stapel[2]++;
			} else if(zweitKleinste == 2 && frei == 0) {
				stapel[2] = stapel[2]--;
				stapel[0] = stapel[0]++;
			} else if(zweitKleinste == 2 && frei == 1) {
				stapel[2] = stapel[2]--;
				stapel[1] = stapel[1]++;
			}
			
			zweitKleinste = frei;
			
			if(kleinste == 0 && zweitKleinste == 2) {
				frei = 1;
			} else if(kleinste == 0 && zweitKleinste == 1) {
				frei = 2;
			} else if(kleinste == 1 && zweitKleinste == 2) {
				frei = 0;
			} else if(kleinste == 1 && zweitKleinste == 0) {
				frei = 2;
			} else if(kleinste == 2 && zweitKleinste == 0) {
				frei = 1;
			} else if(kleinste == 2 && zweitKleinste == 1) {
				frei = 0;
			}
		}
		
		System.out.println("Quelle hat: " + stapel[0] + " Scheiben!");
		System.out.println("Ziel hat: " + stapel[1] + " Scheiben!");
		System.out.println("Hilfsziel hat: " + stapel[2] + " Scheiben!");
	}
	
	public static void main (String args []) {
		tow(3);
	}
}

Aber das terminiert nicht 🙁

 

[PfiffPaff]

Hab mal paar System.outs rein gehaun....

warum mcht er nach dem ersten Schritt:

3 | 0 | 0
1 | 2 | 0

ich hab doch stapel[0]-- und
stapel[1]++

Da müsste doch in Zeile 2 dann stehen

2 | 1 | 0

oO?

 

[PfiffPaff]

Keiner nen Tipp? 🙁

 

[xehpuk]

Was soll

stapel[0] = stapel[0]--;

denn werden? Das dürfte nicht so viel machen. Das sollte wohl

stapel[0]--;

heißen.

 

[PfiffPaff]

Jup das hab ich bereits ausgebessert...

also das hier:

Hab mal paar System.outs rein gehaun....

warum mcht er nach dem ersten Schritt:

3 | 0 | 0
1 | 2 | 0

ich hab doch stapel[0]-- und
stapel[1]++

Da müsste doch in Zeile 2 dann stehen

2 | 1 | 0

oO?

ist immernoch aktuell!

 

[BOBOHelp]

hast du nicht ausgebessert so wie "xehpuk" vorgeschlagen hat, sonnst bekommst [2,1,0]

 

[PfiffPaff]

Ich habs ausgebessert.....

public class HanoiIt {
	
	static void tow(int n) {
		int[] stapel = {n, 0, 0};
		int kleinste = 0;
		int zweitKleinste = 0;
		int frei = 2;
		
		System.out.println("Quelle hat: " + stapel[0] + " Scheiben!");
		System.out.println("Ziel hat: " + stapel[1] + " Scheiben!");
		System.out.println("Hilfsziel hat: " + stapel[2] + " Scheiben!");
		
		while(stapel[0] != 0 && stapel[1] != n) {
			if(kleinste == 0) {
				stapel[0]--;
				stapel[1]++;
			} else if(kleinste == 1) {
				stapel[1]--;
				stapel[2]++;
			} else if(kleinste == 2) {
				stapel[2]--;
				stapel[0]++;
			}
			
			if(kleinste == 2) {
				kleinste = 0;
			} else {
				kleinste++;
			}
			
			
			if(zweitKleinste == 0 && frei == 2) {
				stapel[0]--;
				stapel[2]++;
			} else if(zweitKleinste == 0 && frei == 1) {
				stapel[0]--;
				stapel[1]++;
			} else if(zweitKleinste == 1 && frei == 0) {
				stapel[1]--;
				stapel[0]++;
			} else if(zweitKleinste == 1 && frei == 2) {
				stapel[1]--;
				stapel[2]++;
			} else if(zweitKleinste == 2 && frei == 0) {
				stapel[2]--;
				stapel[0]++;
			} else if(zweitKleinste == 2 && frei == 1) {
				stapel[2]--;
				stapel[1]++;
			}
			
			zweitKleinste = frei;
			
			if(kleinste == 0 && zweitKleinste == 2) {
				frei = 1;
			} else if(kleinste == 0 && zweitKleinste == 1) {
				frei = 2;
			} else if(kleinste == 1 && zweitKleinste == 2) {
				frei = 0;
			} else if(kleinste == 1 && zweitKleinste == 0) {
				frei = 2;
			} else if(kleinste == 2 && zweitKleinste == 0) {
				frei = 1;
			} else if(kleinste == 2 && zweitKleinste == 1) {
				frei = 0;
			}
		}
		
		System.out.println("Quelle hat: " + stapel[0] + " Scheiben!");
		System.out.println("Ziel hat: " + stapel[1] + " Scheiben!");
		System.out.println("Hilfsziel hat: " + stapel[2] + " Scheiben!");
	}
	
	public static void main (String args []) {
		tow(3);
	}
}

Ergebnis ist 1 | 2 | 0 und das Programm terminiert nicht

 

[PfiffPaff]

Also das macht er zur Zeit:

3 | 0 | 0
2 | 1 | 0
1 | 2 | 0

Der dritte Schritt ist mir unverständlich.....

 

[Paddelpirat]

Geh am besten mal mit einem Debugger da durch und schau dir jeden Schritt an.

 

[hüteüberhüte]

Oben die SuFu benutzen und nach "Hanoi iterativ" suchen. Es gibt bestimmt mehr als 5 Themen dazu. Hier mehrere iterative und rekursive Versionen: http://www.java-forum.org/java-basi...14277-tuerme-hanoi-iterator-2.html#post735646
Hier das Suchergebnis: java-forum.org - Suchergebnisse

 

[bfmn]

Hallo PfiffPfaf,

Ich hab deinen Code mal um Ausgaben erweitert und durch den Debugger geschickt.

Was passiert ist:

Quelle hat: 3 Scheiben!
Ziel hat: 0 Scheiben!
Hilfsziel hat: 0 Scheiben!
2 | 1 | 0
1 | 1 | 1
1 | 0 | 2
2 | 0 | 1
3 | 0 | 0
2 | 1 | 0

usw.
Du legst also immer wieder alle Steine zurück auf den stapel[0], was dein Ausgangpunkt ist. Aufjedenfall ist das der Grund wieso dein Programm nicht zu einem Ende kommt, weil die Abbruchbedingung nie erreicht wird. (while(stapel[0] != 0 && stapel[1] != n))

Ich habe noch nicht ganz hinter deine Logik geblickt, würde aber mal beim setzten von kleinste anfangen.
Mir ist nicht ganz klar wieso du den Wert einfach immer um 1 erhöhst und dann zu 0 zurückspringst wenn du 2 erreicht hast.

Leider ist der Akku von meinem Notebook gleich leer, aber viel Glück bei der Fehlersuche.

mfg,
Niko

 

[PfiffPaff]

Hallo bfmn,

ich mache das nach dem Algorithmus den ich in einer PDF gefunden habe:

– Wiederhole solange, bis der gesamte Stapel auf der Zielstange ist
1. Setzte die kleinste Scheibe auf die Stange rechts von ihr (bzw. die erste Stange)
2. Setzte die zweitkleinste Scheibe auf die einzig mögliche Stange

 

[PfiffPaff]

Jetzt hab ich gedacht ich hab den Fehler aber leider doch nicht....
dachte das ich das freie Feld immer falsch gesetzt hatte bekomme
nach korrektur des codes aber immernoch die gleiche Ausgabe:

public class HanoiIt {
	
	static void tow(int n) {
		int[] stapel = {n, 0, 0};
		int kleinste = 0;
		int zweitKleinste = 0;
		
		System.out.println("Quelle hat: " + stapel[0] + " Scheiben!");
		System.out.println("Ziel hat: " + stapel[1] + " Scheiben!");
		System.out.println("Hilfsziel hat: " + stapel[2] + " Scheiben!");
		
		while(stapel[0] != 0 && stapel[1] != n) {
			if(kleinste == 0) {
				stapel[0]--;
				stapel[1]++;
				System.out.println(stapel[0] + " | " + stapel[1] + " | " + stapel[2]);
			} else if(kleinste == 1) {
				stapel[1]--;
				stapel[2]++;
				System.out.println(stapel[0] + " | " + stapel[1] + " | " + stapel[2]);
			} else if(kleinste == 2) {
				stapel[2]--;
				stapel[0]++;
				System.out.println(stapel[0] + " | " + stapel[1] + " | " + stapel[2]);
			}
			
			if(kleinste == 2) {
				kleinste = 0;
			} else {
				kleinste++;
			}
			
			
			if(zweitKleinste == 0 && kleinste == 1) {
				stapel[0]--;
				stapel[2]++;
				zweitKleinste = 2;
				System.out.println(stapel[0] + " | " + stapel[1] + " | " + stapel[2]);
			} else if(zweitKleinste == 0 && kleinste == 2) {
				stapel[0]--;
				stapel[1]++;
				zweitKleinste = 1;
				System.out.println(stapel[0] + " | " + stapel[1] + " | " + stapel[2]);
			} else if(zweitKleinste == 1 && kleinste == 0) {
				stapel[1]--;
				stapel[2]++;
				zweitKleinste = 2;
				System.out.println(stapel[0] + " | " + stapel[1] + " | " + stapel[2]);
			} else if(zweitKleinste == 1 && kleinste == 2) {
				stapel[1]--;
				stapel[0]++;
				zweitKleinste = 0;
				System.out.println(stapel[0] + " | " + stapel[1] + " | " + stapel[2]);
			} else if(zweitKleinste == 2 && kleinste == 0) {
				stapel[2]--;
				stapel[1]++;
				zweitKleinste = 1;
				System.out.println(stapel[0] + " | " + stapel[1] + " | " + stapel[2]);
			} else if(zweitKleinste == 2 && kleinste == 1) {
				stapel[2]--;
				stapel[0]++;
				zweitKleinste = 0;
				System.out.println(stapel[0] + " | " + stapel[1] + " | " + stapel[2]);
			}
		}
		
		System.out.println("Quelle hat: " + stapel[0] + " Scheiben!");
		System.out.println("Ziel hat: " + stapel[1] + " Scheiben!");
		System.out.println("Hilfsziel hat: " + stapel[2] + " Scheiben!");
	}
	
	public static void main (String args []) {
		tow(3);
	}
}

/*
3 | 0 | 0
2 | 1 | 0
1 | 1 | 1
1 | 0 | 2
2 | 0 | 1
2 | 1 | 0
1 | 2 | 0
1 | 1 | 1
2 | 0 | 1
*/

 

[Paddelpirat]

Der Fehler tritt ja dann hier in dieser Zeile auf:

2 | 1 | 0
1 | 1 | 1
1 | 0 | 2
2 | 0 | 1<--
3 | 0 | 0
2 | 1 | 0

In der markierten Zeile müsstest du wohl merken, dass das die kleinste Scheibe ganz rechts ist und dann die große Scheibe von Stange 1 auf Stange 2 schieben. Dann verschiebst du die kleine Scheibe auf die freie Scheibe und die mittlere Scheibe auf die zweite Stange. Dann wieder die kleine auf die mittlere... fertig.

 

[PfiffPaff]

Richtig, genau in der Zeile, deshalb weiß ich auch nicht was falsch sein soll...
Denn schließlich ist die größte Scheibe ganz links jetzt die "zweitKleinste" weil
die kleinste ganz Rechts ist, sie wird aber nicht verschoben und ich weiß nicht wieso

 

[PfiffPaff]

Okay, ich weiß wo der fehler liegt....

der Fehler liegt hier:

if(kleinste == 2) {
	kleinste = 0;
} else {
	kleinste++;
}

wenn ich die kleinste auf die zweitkleinste lege,
muss ich auch die Position des zweitkleinsten ändern....

 

[Paddelpirat]

Du sagst aber nirgendwo, dass die Scheibe ganz links die zweitkleinste ist. Das müsstest du dann wohl in Zeile 20 oder so machen.