Türme von Hanoi

Die Türme von Hanoi sind ein klassisches Beispiel für einen rekursiven Algorithmus. Bei diesem Spiel müssen mehrere verschieden große Scheiben von einem Quellstapel auf einen Zielstapel gebracht werden. Dabei darf aber immer nur eine Scheibe bewegt werden, zudem darf immer nur eine kleinere Scheibe auf einer größeren Scheibe liegen. Das folgende Bild illustriert das Spiel (Quelle Wikipedia):

Eine rekursive Herangehensweise beschreibt die Lösung des Problems folgendermaßen: Wenn du n Scheiben vom Quell- auf den Zielstapel bringen willst, dann verschiebe zunächst n-1 Scheiben auf den Hilfsstapel, dann 1 Scheibe (die unterste) auf den Zielstapel und zum Schluss n-1 Scheiben vom Hilfs- auf den Zielstapel.

Der folgende Java-Algorithmus setzt voraus, dass die drei Stapel mit 1, 2, 3 durchnummeriert sind. Zu Beginn wird die Methode also beispielsweise zur Lösung des 5-Scheiben-Problems mit den Parametern 5, 1, 3, 2 aufgerufen. Die Scheibenbewegungen werden durch Bildschirmausdrucke dargestellt.

public class Hanoi {

    public void TvH(int n, int start, int ziel, int hilf) {

        if (n==1) {
            System.out.println(start+" -> "+ziel);
        }
        else {
            TvH(n-1, start, hilf, ziel);
            TvH(  1, start, ziel, hilf);
            TvH(n-1, hilf,  ziel, start);
        }
    }

}

Für das 5-Scheiben-Problem ergibt sich demnach folgende Ausgabe:

1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3
1 -> 2
3 -> 2
3 -> 1
2 -> 1
3 -> 2
1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3
2 -> 1
3 -> 2
3 -> 1
2 -> 1
2 -> 3
1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3

results matching ""

    No results matching ""