Türme von Hanoi Iterativ

[wuerg]

Hallo Leute!

Ich habe den rekursiven Code Türme von Hanoi (Quelle: Kopec Algorithmen in Java) versucht iterativ zu programmieren. Mein Code funktioniert auch. Aber, ich vermute, dass es einfacher geht. Hier mein "Erguß":

// HanoiIt.java

import java.util.Stack;

public class HanoiIt {
public static final Stack<Integer> towerA = new Stack<>();
public static final Stack<Integer> towerB = new Stack<>();
public static final Stack<Integer> towerC = new Stack<>();

public HanoiIt(int discs) {
for (int i = 1; i <= discs; i++) {
towerA.push(i);
}
}

public static void main(String[] args) {
HanoiIt hanoi = new HanoiIt(3);
System.out.println( "aufgefuellter Turm A:" + hanoi.towerA);
for(int i=0; i < towerA.size(); i++){
System.out.println( "Elemente am Turm A:" + towerA.get(i));
}
while ( towerC.size() != 3 ) {
if ( towerA.size() == 3) {
towerA.pop();
towerC.push(3);
towerA.pop();
towerB.push(2);
System.out.println("Schritt 1:");
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
}
else if ((towerA.size() == 1) && (towerB.size() == 1) && (towerC.size() == 1)) {
towerC.pop();
towerB.push(3);
towerA.pop();
towerC.push(1);
System.out.println("Schritt 2:");
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
}
else if (towerB.size() == 2) {
towerB.pop();
towerA.push(3);
towerB.pop();
towerC.push(2);
System.out.println("Schritt 3:");
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
}
else if ((towerA.size() != 0) || (towerB.size() != 0)) {
towerA.pop();
towerC.push(3);
System.out.println("Schritt 4:");
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
}
}
System.out.println("Hanoi-Tuerme fertig sortiert");
}
}

Kommt mir etwas "unhandlich" vor. Bitte um Verbesserungsideen.

Danke

Euer Wuerg

 

[wuerg]

Habe den Code nun selbst verbessert. Für drei Türme und drei Scheiben funktioniert er. Habe zwei Versionen erstellt. Eine dokumentierte und eine undokumentierte:

Dokumentiert:

import java.util.Stack;

public class PseuCo_kommentiert {
private final int numDiscs;
public static final Stack<Integer> towerA = new Stack<>();
public static final Stack<Integer> towerB = new Stack<>();
public static final Stack<Integer> towerC = new Stack<>();

public PseuCo_kommentiert(int discs) {
numDiscs = discs;
for (int i = 1; i <= discs; i++) {
towerA.push(i);
}
System.out.println( "aufgefuellter Turm A:" + towerA);
}

public static void main(String[] args) {
PseuCo_kommentiert hanoi = new PseuCo_kommentiert(3);

int a = 3, b = 0, c = 0, i = 0, x = 3, z = 0; //x = Anzahl der Scheiben; a, b, c = Türme; z = Schrittanzahl; i = Anzahl der Scheiben auf C

while ( i != x ) {
if ( i == x - 1 && b == x ) {
towerB.pop();
c = b;
towerC.push(b);
if ( towerB.isEmpty() ) { b = 0; } else { b = towerB.peek(); };
z = z + 1;
i = i + 1;
System.out.println("Schritt:" + z );
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
System.out.println("a = " + a );
System.out.println("b = " + b );
System.out.println("c = " + c );
System.out.println("i = " + i );
System.out.println("x = " + x );
System.out.println("Türme fertig sortiert !");
}
else if ( towerA.empty() ) {
towerC.pop();
a = c;
towerA.push(c);
if ( towerC.isEmpty() ) { c = 0; } else { c = towerC.peek(); };
z = z + 1;
i = i - 1; // wenn keiner der Türme leer ist, muss ich die Anzahl der Scheiben auf Turm C wieder dekrementieren
System.out.println("Schritt:" + z );
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
System.out.println("a = " + a );
System.out.println("b = " + b );
System.out.println("c = " + c );
System.out.println("i = " + i );
System.out.println("x = " + x );
}
else if ( towerB.empty() ) {
towerA.pop();
b = a;
towerB.push(a);
if ( towerA.isEmpty() ) { a = 0; } else { a = towerA.peek(); };
z = z + 1;
System.out.println("Schritt:" + z );
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
System.out.println("a = " + a );
System.out.println("b = " + b );
System.out.println("c = " + c );
System.out.println("i = " + i );
System.out.println("x = " + x );
}
else if ( towerC.empty() ) {
towerB.pop();
c = b;
towerC.push(b);
if ( towerB.isEmpty() ) { b = 0; } else { b = towerB.peek(); };
z = z + 1;
i = i + 1;
System.out.println("Schritt:" + z );
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
System.out.println("a = " + a );
System.out.println("b = " + b );
System.out.println("c = " + c );
System.out.println("i = " + i );
System.out.println("x = " + x );
}
else if ( b > 0 && a > b && c != i && a == x ) {
towerA.pop();
b = a;
towerB.push(a);
if ( towerA.isEmpty() ) { a = 0; } else { a = towerA.peek(); };
z = z + 1;
System.out.println("Schritt:" + z );
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
System.out.println("a = " + a );
System.out.println("b = " + b );
System.out.println("c = " + c );
System.out.println("i = " + i );
System.out.println("x = " + x );
}
else if ( c > 0 && b > c ) { // && c != i && b == x
towerB.pop();
c = b;
towerC.push(b);
if ( towerB.isEmpty() ) { b = 0; } else { b = towerB.peek(); };
z = z + 1;
i = i + 1;
System.out.println("Schritt:" + z );
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
System.out.println("a = " + a );
System.out.println("b = " + b );
System.out.println("c = " + c );
System.out.println("i = " + i );
System.out.println("x = " + x );
}
else if ( a > 0 && c > a && c != i && c == x ) {
towerC.pop();
a = c;
towerA.push(c);
if ( towerC.isEmpty() ) { c = 0; } else { c = towerC.peek(); };
z = z + 1;
i = i - 1; // wenn keiner der Türme leer ist, muss ich die Anzahl der Scheiben auf Turm C wieder dekrementieren
System.out.println("Schritt:" + z );
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
System.out.println("a = " + a );
System.out.println("b = " + b );
System.out.println("c = " + c );
System.out.println("i = " + i );
System.out.println("x = " + x );
}
}
}
}

Und nun die undokumentierte (mit klarerweise weniger Codezeilen):

import java.util.Stack;

public class PseuCo {
private final int numDiscs;
public static final Stack<Integer> towerA = new Stack<>();
public static final Stack<Integer> towerB = new Stack<>();
public static final Stack<Integer> towerC = new Stack<>();

public PseuCo(int discs) {
numDiscs = discs;
for (int i = 1; i <= discs; i++) {
towerA.push(i);
}
System.out.println( "aufgefuellter Turm A:" + towerA);
}

public static void main(String[] args) {
PseuCo hanoi = new PseuCo(3);

int a = 3, b = 0, c = 0, i = 0, x = 3, z = 0; //x = Anzahl der Scheiben; a, b, c = Türme; z = Schrittanzahl; i = Anzahl der Scheiben auf C

while ( i != x ) {
if ( i == x - 1 && b == x ) {
towerB.pop();
c = b;
towerC.push(b);
if ( towerB.isEmpty() ) { b = 0; } else { b = towerB.peek(); };
z = z + 1;
i = i + 1;
System.out.println("Schritt:" + z );
System.out.println("Turm A:" + hanoi.towerA);
System.out.println("Turm B:" + hanoi.towerB);
System.out.println("Turm C:" + hanoi.towerC);
System.out.println("Türme fertig sortiert !");
}
else if ( towerA.empty() ) {
towerC.pop();
a = c;
towerA.push(c);
if ( towerC.isEmpty() ) { c = 0; } else { c = towerC.peek(); };
z = z + 1;
i = i - 1; // wenn keiner der Türme leer ist, muss ich die Anzahl der Scheiben auf Turm C wieder dekrementieren
}
else if ( towerB.empty() ) {
towerA.pop();
b = a;
towerB.push(a);
if ( towerA.isEmpty() ) { a = 0; } else { a = towerA.peek(); };
z = z + 1;
}
else if ( towerC.empty() ) {
towerB.pop();
c = b;
towerC.push(b);
if ( towerB.isEmpty() ) { b = 0; } else { b = towerB.peek(); };
z = z + 1;
i = i + 1;
}
else if ( b > 0 && a > b && c != i && a == x ) {
towerA.pop();
b = a;
towerB.push(a);
if ( towerA.isEmpty() ) { a = 0; } else { a = towerA.peek(); };
z = z + 1;
}
else if ( c > 0 && b > c ) {
towerB.pop();
c = b;
towerC.push(b);
if ( towerB.isEmpty() ) { b = 0; } else { b = towerB.peek(); };
z = z + 1;
i = i + 1;
}
else if ( a > 0 && c > a && c != i && c == x ) {
towerC.pop();
a = c;
towerA.push(c);
if ( towerC.isEmpty() ) { c = 0; } else { c = towerC.peek(); };
z = z + 1;
i = i - 1; // wenn keiner der Türme leer ist, muss ich die Anzahl der Scheiben auf Turm C wieder dekrementieren
}
}
}
}

Der Code wurde mit Java 19 kompiliert. Müßte aber ab Java 11 kompilierbar sein!

 

[weihnachtspyramide]

Wer soll das lesen? Der Code ist schlecht formatiert und schlecht geschrieben.

 

[yfons123]

Wer soll das lesen? Der Code ist schlecht formatiert und schlecht geschrieben.

du weist dass türme von hanoi extrem komplex ist wenn du es interativ machst

 

[weihnachtspyramide]

du weist dass türme von hanoi extrem komplex ist wenn du es interativ machst

Ja schon, aber gerade dann sollte er doch bitte den Code formatieren.

 

[yfons123]

also wenn ich die datei öffne ist die ziemlich gut formatiert

ja gut hat am ende der zeilen mal ein paar unnötige spaces dran.. meine jüte die könnte man noch weg machen

 

[mihe7]

Mal ein kleines Refactoring:

import java.util.Stack;

public class PseuCo_kommentiert {
    private final int numDiscs;
    private final Tower towerA;
    private final Tower towerB;
    private final Tower towerC;

    public PseuCo_kommentiert(int discs) {
        numDiscs = discs;
        towerA = new Tower("A", numDiscs);
        towerB = new Tower("B");
        towerC = new Tower("C");
        System.out.println("aufgefuellter Turm A:" + towerA);
    }

    public void run() {
        int step = 0;
        final int smallestDisc = numDiscs;
        while (towerC.size() != numDiscs) {
            if (towerC.size() == numDiscs - 1 && towerB.hasOnTop(smallestDisc)) {
                towerB.moveTopTo(towerC);
            } else if (towerA.isEmpty()) {
                towerC.moveTopTo(towerA);
            } else if (towerB.isEmpty()) {
                towerA.moveTopTo(towerB);
            } else if (towerC.isEmpty()) {
                towerB.moveTopTo(towerC);
            } else if (towerA.canMoveTopTo(towerB) && towerC.mustReorder() && towerA.hasOnTop(smallestDisc)) {
                towerA.moveTopTo(towerB);
            } else if (towerB.canMoveTopTo(towerC)) {
                towerB.moveTopTo(towerC);
            } else if (towerC.canMoveTopTo(towerA) && towerC.mustReorder() && towerC.hasOnTop(smallestDisc)) {
                towerC.moveTopTo(towerA);
            }
            step++;
            printState(step);
        }
    }

    private void printState(int step) {
        System.out.println("Schritt:" + step);
        System.out.println("Turm A:" + towerA);
        System.out.println("Turm B:" + towerB);
        System.out.println("Turm C:" + towerC);
        System.out.println("Anzahl Scheiben = " + numDiscs);
        System.out.println("Türme fertig sortiert !");
    }   

    public static void main(String[] args) {
        PseuCo_kommentiert hanoi = new PseuCo_kommentiert(3);
        hanoi.run();
    }

    // zur Vereinfachung kompakt und als innere Klasse
    // besser schön formatiert nach Tower.java verschieben

    static class Tower {
        private final String name;
        private final Stack<Integer> discs = new Stack<>();
        public Tower(String name) { this(name, 0); }
        public Tower(String name, int initialDiscs) {
            this.name = name;
            for (int i = 1; i <= initialDiscs; i++) {
                discs.push(i);
            }
        }
        public boolean isEmpty() { return discs.isEmpty(); }
        public int size() { return discs.size(); }
        public int getTopDisc() { return isEmpty() ? 0 : discs.peek(); }
        public boolean canMoveTopTo(Tower tower) { return !isEmpty() && getTopDisc() >= tower.getTopDisc(); }
        public boolean mustReorder() { return getTopDisc() != size(); }
        public boolean hasOnTop(int disc) { return getTopDisc() == disc; }
        public void moveTopTo(Tower tower) {
            requiresValidMove(tower);
            tower.discs.push(discs.pop());
        }
        private void requiresValidMove(Tower tower) {
            if (isEmpty()) {
                throw new IllegalArgumentException("Can't move disc to tower " + tower.name + 
                        " since tower " + tower.name + " is empty.");
            }
            
            if (getTopDisc() < tower.getTopDisc()) {
                throw new IllegalArgumentException("Can't move disc " + getTopDisc() + " from tower " + name +
                        " since it's larger than disc " + tower.getTopDisc() + " on top of tower " + tower.name);
            }
        }
        @Override
        public String toString() {
            return "Tower[name=" + name + ", discs = " + discs.toString() + "]";
        }
    }
}

 

[wuerg]

Hallo mihe7!

Wow, geiler Code.

Allerdings die Meldung "System.out.println("Türme fertig sortiert !");" im "printState" bedingt, dass sie bei jedem Schritt ausgegeben wird. Das schau ich mir an!

 

[mihe7]

Wow, geiler Code.

Das ist eigentlich Dein Code, ich habe den nur etwas umgestellt, den Variablen Namen mit mehr Aussagekraft gegeben und eine Klasse für die Türme eingeführt Gut, dann sieht man einige Dinge auch etwas klarer, z. B. dass die Prüfung auf a > 0 (analog für b und c) in den else-Zweigen überflüssig ist, weil der Fall a == 0 (analog für b, c) weiter oben bereits behandelt wurde.

Allerdings die Meldung "System.out.println("Türme fertig sortiert !");" im "printState" bedingt, dass sie bei jedem Schritt ausgegeben wird. Das schau ich mir an!

Ein typischer Copy & Paste Fehler