Türme von Hanoi

[Tenacious]

Nabend,

ja ich weiß das Thema wurde hier schon bestimmt 100-mal durchgekaut, aber ich konnte in keinem Thread Antworten zu meinen Fragen finden 🙂

Die Aufgabe ist die folgende:

"Nun soll auf der zuvor implementierten Datenstruktur aufbauend ein Algorithmus programmiert
werden. Unter http://de.wikipedia.org/wiki/Türme_von_Hanoi finden Sie die Beschreibung
des umzusetzenden rekursiven Algorithmus (Randoffscher Algorithmus). Erstellen Sie eine Klasse
TuermeVonHanoi. Ihr Programm bekommt als Konsolenparameter die Anzahl der Scheiben übergeben.
Anschließend soll der rekursive Algorithmus angewandt werden, um den Turm zu verschieben. Jeder
Stab entspricht somit einem Objekt der Klasse StackHanoi. Ihr Algorithmus muss auf diesen Objekten
arbeiten und die Scheiben mittels der in der vorherigen Aufgabe implementierten Methoden bewegen
(hier erfolgt keine Ausgabe auf der Konsole!). Anschließend soll auf der Konsole ausgegeben werden,
wie viele Verschiebungen durchgeführt werden mussten. Zudem soll der Turm auf dem Zielstab
ausgegeben werden. Eine Scheibe der Länge 1 wird durch den String "/\" dargestellt, eine Scheibe
der Länge 2 durch "/\/\" usw.
Der Aufruf
java TuermeVonHanoi 4

würde folgende Ausgabe erzeugen:

Es wurden 15 Verschiebungen benoetigt um 4 Scheiben zu verschieben.
/\
/\/\
/\/\/\
/\/\/\/\"





Mit der "zuvor implementierten Datenstruktur" ist meine erste Aufgabe (von der ich mir eigentlich ziemlich sicher bin, dass sie soweit richtig ist) gemeint:

class stackHanoi 
{
	String[] values; // Stab
	int position; // Position der obersten Scheibe | wenn -1, dann Stab leer
	
	public stackHanoi() // Konstruktor 1
	{
		position = -1;
		values = new String[1];
	}
	
	public stackHanoi(int anzahlScheiben) // Konstruktor 2
	{
		position = -1;
		values = new String[anzahlScheiben];
	}
	
	
	String top() 
	// Gibt die oberste Scheibe zurueck
	{
		if (position != -1)
		{
			return values[position];
		}
		
		System.out.println("Der Stab ist leer!");
		System.exit(1);
		return "";
	}
	
	void pop() 
	// Entfernt die oberste Scheibe
	{
		if (position == -1)
			// Ueberprueft ob der Stab leer ist oder nicht
		{
			System.out.println("Der Stab ist leer!");
			System.exit(1);
		}
		else
		{
			values[position] = "";
			position--;
		}
	}
	
	void push(String neueScheibe)
	// Fuegt eine neue Scheibe hinzu
	{
		if (position == values.length - 1) 
			// Ueberprueft ob der Stab voll ist
		{
			System.out.println("Der Stab ist voll.");
			System.exit(1);
		}
		
		if (neueScheibe.length() > values[position].length()) 
			// Ueberprueft die Scheibe zu groß ist
		{
			System.out.println("Scheibe ist zu groß.");
			System.exit(1);
		}
		
		if (position == -1 || neueScheibe.length() < values[position].length())
			// Fuegt die Scheibe hinzu, wenn Stab leer oder die neue Scheibe kleiner ist
			// als die oberste Scheibe
		{
			values[position+1] = neueScheibe;
			position++;
		}		
	}
	
	int size() // Gibt die Anzahl der Scheiben zurück
	{
		return (position+1);
	}
	
}

Ich versteh nur nicht ganz die Aufgabe die ich nun habe.
- Heißt das, dass ich 3 verschieden Objekte erstellen muss also quasi stab1, stab2, stab3?
- Wie soll ich den Algorithmus von Wikipedia umsetzen wenn mir Methoden wie zum Beispiel "bewege" gar nicht zur Verfügung stehen?
- Wie setze ich die Strings mit "/\" usw. um?


Danke schonmal für eure Hilfe 🙂

 

[Timothy Truckle]

Ich versteh nur nicht ganz die Aufgabe die ich nun habe.
- Heißt das, dass ich 3 verschieden Objekte erstellen muss also quasi stab1, stab2, stab3?

Ja, steht ja genau so in der Aufgabe.
Ich hoffe nur, Du kennst den Unterschied zwischen Klasse und Objekt...

- Wie soll ich den Algorithmus von Wikipedia umsetzen wenn mir Methoden wie zum Beispiel "bewege" gar nicht zur Verfügung stehen?

In dem Du diese Methoden programmierst?

- Wie setze ich die Strings mit "/\" usw. um?

genau so.

bye
TT

 

[hüteüberhüte]

Ich hab das mal implementiert:

    static class Stab {

        final Deque<Integer> scheiben;
        final String name;

        Stab(int anzahl, String name) {
            scheiben = new ArrayDeque<Integer>();
            for (int i = anzahl; i > 0; i--) {
                scheiben.add(i);
            }
            this.name = name;
        }

        void bewegeNach(Stab s) {
            if (scheiben.isEmpty() || !s.scheiben.isEmpty() && scheiben.getLast() > s.scheiben.getLast()) {
                throw new IllegalArgumentException("empty or greater than s");
            }
            s.scheiben.add(scheiben.removeLast());
            System.out.printf("von %s nach %s%n", name, s.name);
        }

        @Override
        public String toString() {
            return name + " = Stab{" + "scheiben=" + scheiben + '}';
        }
    }

    public static void bewege(int i, Stab a, Stab b, Stab c, Stab[] alle) {
        if (i <= 0) {
            return;
        }
        bewege(i - 1, a, c, b, alle);
        a.bewegeNach(c);

        for (Stab stab : alle) {
            System.out.print(stab + ", ");
        }
        System.out.println("");
        System.out.println("");

        bewege(i - 1, b, a, c, alle);
    }

    public static void main(String[] args) {
        final int n = 3;
        final Stab A = new Stab(n, "A"), B = new Stab(0, "B"), C = new Stab(0, "C");
        bewege(n, A, B, C, new Stab[]{A, B, C});
    }

Ist nicht so schön, weil a) Ausgaben drin sind und b) mir netbeans sagt, Exporting non-public type through public api (Stab ist nicht öffentlich), und c) ich einen vierten Parameter benötige, der sich die Reihenfolge der Stäbe merkt. 🙁

 

[hüteüberhüte]

Jetz kann man natürlich darüber streiten, ob man Keller, Wand, Dach oder Dach, Wand, Keller sagt. Letzteres finde ich unintuitiv. 😉

 

[Nacho]

Hallo zusammen!
Ich hätte da auch eine Frage bzgl der Türme. Mein Quelltext sieht wie folgt aus:

	public static void main(String args[]) {
		System.out.println("Tuerme von Hanoi");
		Tow("Quelle", "Hilfsziel", "Ziel", 5);
	}

	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 + " hier kommt HILF: " + Hilf);
			Tow(Hilf, Quelle, Ziel, n - 1);
		}
	}

Die Aufgabe ist nun eine Ausgabe zu erzeugen die das verschieben der einzelnen Scheiben zeigt. Ich hab bereits das ganze schon mit einem 2 dimensionallen Array welches einmal den Turm angibt und dann die jeweilige scheibe abspeichert. Eine zusätzliche Methode bedient sich dann des Array und gibt dann bspw dann für 4 Scheiben für eine Verschiebung wie folgt aus:

     |            |            |     
     |            |            |     
  ###|###         |            |     
 ####|####       #|#         ##|##   
-----------  -----------  -----------

Hat jemand eine Idee wie man das gleiche Ergebniss ohne Array, nur anhand einer Rekursion in den oben aufgeführten Code unterbringt?

 

[hüteüberhüte]

Das Problem dürfte sein, dass die Parameter vertauscht werden und somit die Reihenfolge der Stäbe/Scheiben nicht mehr gegeben ist, diese brauchst du aber für die Ausgabe.

Btw, zeig mal den Quelltext, der diese Ausgabe erstellt.

 

[Nacho]

Hier der Code. Würd mich über Verbesserungsvorschläge freuen.

public static void main(String[] args) {
			int anzahl = 4;

			bob = new int[3][anzahl];
			fill(anzahl);
			turm(bob[0], bob[1], bob[2], anzahl);
			printVar(0, 3 * (2 * bob[0].length + 3) + 2, anzahl);
			System.out.println(anzahl + " Scheiben müssen insgesamt " + counter + " mal verschoben werden.");
		}

		private static int[][] bob;
		private static int counter = 0;

		private static void printVar(int spalte, int stelle, int anzahl) {
			if (spalte >= bob[0].length) {
				boden(3 * (2 * anzahl + 3) + 2, anzahl);
				return;
			}
			if (stelle == 0) {
				System.out.println();
				printVar(spalte + 1, 3 * (2 * anzahl + 3) + 2, anzahl);
				return;
			}
			if (stelle % (2 * anzahl + 4) == 0) {
				System.out.print("  ");
				printVar(spalte, stelle - 1, anzahl);
				return;
			}
			if (stelle % (2 * anzahl + 4) == (anzahl + 2)) {
				System.out.print("|");
				printVar(spalte, stelle - 1, anzahl);
				return;
			} else if (stelle > 2 * (2 * anzahl + 4)) {
				if ((stelle - 2 * (2 * anzahl + 4)) <= (anzahl + 2)
						+ bob[0][spalte]
						&& (stelle - 2 * (2 * anzahl + 4)) >= (anzahl + 2)
								- bob[0][spalte])
					System.out.print("#");
				else
					System.out.print(" ");
			} else if (stelle < 2 * (2 * anzahl + 4) && stelle > (2 * anzahl + 4)) {
				if ((stelle - (2 * anzahl + 4)) <= (anzahl + 2) + bob[1][spalte]
						&& (stelle - (2 * anzahl + 4)) >= (anzahl + 2)
								- bob[1][spalte])
					System.out.print("#");
				else
					System.out.print(" ");
			} else {
				if (stelle <= (anzahl + 2) + bob[2][spalte]
						&& stelle >= (anzahl + 2) - bob[2][spalte])
					System.out.print("#");
				else
					System.out.print(" ");
			}
			printVar(spalte, stelle - 1, anzahl);
		}

		private static void boden(int stelle, int anzahl) {
			if (stelle == 0) {
				System.out.println("\n\n");
				return;
			}
			if (stelle % (2 * anzahl + 4) == 0) {
				System.out.print("  ");
				boden(stelle - 1, anzahl);
			} else {
				System.out.print("-");
				boden(stelle - 1, anzahl);
			}
		}

		private static void turm(int[] eins, int[] zwei, int[] drei, int anzahl) {
			if (anzahl == 1)
				move(eins, drei, 0, 0);
			else {
				turm(eins, drei, zwei, anzahl - 1);
				move(eins, drei, 0, 0);
				turm(zwei, eins, drei, anzahl - 1);
			}
		}

		private static void move(int[] von, int[] nach, int stelleVon,
				int stelleNach) {
			if (von[stelleVon] == 0) {
				move(von, nach, stelleVon + 1, stelleNach);
				return;
			}
			if (stelleNach + 1 != nach.length && nach[stelleNach + 1] == 0) {
				move(von, nach, stelleVon, stelleNach + 1);
				return;
			}
			printVar(0, 3 * (2 * bob[0].length + 3) + 2, bob[0].length);
			nach[stelleNach] = von[stelleVon];
			von[stelleVon] = 0;
			counter++;
		}
	
		private static void fill(int anzahl) {
			if (anzahl == 0)return;
			bob[0][bob[0].length - anzahl] = bob[0].length - anzahl + 1;
			fill(anzahl - 1);
		}

 

[SlaterB]

du bist ja von Rekursion fasziniert, das sieht man selten,
die Methode move() könnte ohne die letzten beiden Parameter auskommen und muss sich nicht selber aufrufen,
gehe in je einer Schleife die beiden Arrays durch, suche die letzten Indexe mit Wer != 0 und dann hast du die benötigten Stellen

fill() am Anfang ginge mit einer Schleife auch, ist aber nur kleine Sache

am wichtigsten ist natürlich die verrückte printVar()-Methode,
allein schon beim Aufruf [c]printVar(0, 3 * (2 * bob[0].length + 3) + 2, bob[0].length);[/c]
von move() aus kann man in Ohnmacht fallen, was soll diese komplizierte Zeile bedeuten?

auf das an sich zu Erwartende, 'gib den aktuellen Stand aus', hätte wohl kaum wer getippt,
es ist ein Unding, Details der Darstellung mitten in der move()-Methode auszubreiten,
[c]printAll();[/c] oder so wäre angebracht,
und sei es nur eine Dummy-Methode nahe printVar(), die dann [c]printVar(0, 3 * (2 * bob[0].length + 3) + 2, bob[0].length);[/c] aufruft,
mag nur eine Spielerei, ein Verschieben sein, aber es ist wichtig dass man den Anzeige-Code mit seinen Details an einer Stelle findet,
stell dir vor es gäbe noch eine zweite Programmstelle die die Ausgabe starten will, soll dort wieder die komplizierte Zeile stehen oder nur printAll()?
aha, in der main-Methode steht ja sogar eine zweite Ausgabe, erwischt 😉

freilich sowieso keine drei so komplizierten Parameter, keine Rekursion für die Ausgabe,
keine hundertfach berechneten [c](2 * anzahl + 4)[/c] usw.,

wobei es superkurz auch nicht leicht geht, hier eine Variante von mir, noch bisschen geschönt durch p()-Methode,
ich denke durch die Schleifen hat man einen weitaus besseren Überblick zum Ablauf, oder hast du grundsätzlich was dagegen, für die Aufgabe verboten?

das muss doch ein Missverständnis sein, für die Turmbewegung natürlich Rekursion, aber für Ausgabe usw.,
da ist ohne Schleifen nur unleserlicher Code die Folge,
wobei es auch noch etwas besser ginge durch Strukturierung, printVar() nutzt du ja auf verschiedenste Weise,
wenn dann mehr Untermethoden für Zeichnen eines Turms usw., boden() hast du zum Glück separat

    private static void printAll()
    {
        int hoehe = bob[0].length;
        int breiteTurmH = hoehe + 1;
        int breiteTurm = breiteTurmH * 2 + 1;

        System.out.println();

        for (int i = 0; i < hoehe; i++)
        {
            for (int j = 0; j < bob.length; j++)
            {
                int scheibe = bob[j][i];
                p(" ", breiteTurmH - scheibe);
                p("#", scheibe);
                p("|");
                p("#", scheibe);
                p(" ", breiteTurmH - scheibe);
                p("  "); // wird im Moment auch hinter dem letzten Turm ausgegeben, gegebenfalls if 
            }
            System.out.println("");
        }
        for (int j = 0; j < bob.length; j++)
        {
            p("-", breiteTurm);
            p("  "); // wird im Moment auch hinter dem letzten Turm ausgegeben, gegebenfalls if 
        }
        System.out.println("");
    }

    private static void p(String st, int n)
    {
        for (int k = 0; k < n; k++) p(st);
    }

    private static void p(String st)
    {
        System.out.print(st);
    }

 

[Nacho]

Super, danke für die Antwort 🙂

Was die rekursion angeht: Aus Übungsgründen sollten wir ganz auf Schleifen verzichten 😉
Ich schau mir das mal an, wenn ich noch Fragen haben sollte meld ich mich 🙂

 

[SlaterB]

naja, dann steht in meiner Antwort nicht grad viel 😉

wobei du den Programmaufbau bei der Ausgabe immer noch etwas nachbauen kannst,
statt Schleifen Rekursion, aber eine Methode für die 4 Zeilen, dann eine Methode für den Turm einzeln usw.,
auch p() mit der Schleife,
aber muss ja nicht genau meine Variante werden