Turm von Hanoi – Algorithmus und Implementierung in Java
Tags:
* Algorithmus
* Turm von Hanoi
* Rekursion
* Java-Implementierung
Einleitung
Der Turm von Hanoi ist ein klassisches Rätselspiel, das es seit Jahrhunderten gibt. Das Ziel des Spiels ist es, alle Scheiben von einem Stab auf einen anderen zu verschieben, wobei immer nur eine Scheibe gleichzeitig bewegt werden darf und eine größere Scheibe niemals auf eine kleinere gelegt werden darf. Die Schwierigkeit des Spiels nimmt mit der Anzahl der Scheiben zu.
In der Informatik wird der Turm von Hanoi als klassisches Beispiel für Rekursion verwendet. Rekursion ist eine Programmiertechnik, bei der eine Funktion sich selbst aufruft. Dies wird verwendet, um komplexe Probleme in kleinere Teilprobleme aufzuteilen, die dann Schritt für Schritt gelöst werden.
Algorithmus
Der Algorithmus für den Turm von Hanoi kann rekursiv wie folgt beschrieben werden:
1. Wenn nur eine Scheibe vorhanden ist, verschiebe sie auf den Zielstab.
2. Andernfalls:
* Verschiebe die oberste Scheibe vom Quellstab auf den Zwischenstab.
* Rufe den Algorithmus rekursiv auf, um den verbleibenden Turm von der Quelle zum Ziel zu verschieben.
* Rufe den Algorithmus rekursiv auf, um die einzelne Scheibe vom Zwischenstab zum Ziel zu verschieben.
Implementierung in Java
Die folgende Java-Implementierung des Turms von Hanoi zeigt, wie der rekursive Algorithmus in Code umgesetzt wird:
java
public class TowerOfHanoi {
// Anzahl der Scheiben
private int n;
/**
* Konstruktor
* @param n Anzahl der Scheiben
*/
public TowerOfHanoi(int n) {
this.n = n;
}
/**
* Turm von Hanoi lösen
* @param source Quellstab
* @param destination Zielstab
* @param auxiliary Zwischenstab
*/
public void solve(String source, String destination, String auxiliary) {
if (n == 1) {
System.out.println("Scheibe 1 von " + source + " nach " + destination + " verschoben");
} else {
solve(source, auxiliary, destination);
System.out.println("Scheibe " + n + " von " + source + " nach " + destination + " verschoben");
solve(auxiliary, destination, source);
}
}
public static void main(String[] args) {
TowerOfHanoi towerOfHanoi = new TowerOfHanoi(3);
towerOfHanoi.solve("A", "C", "B");
}
}
Beispiel
Wenn wir die Java-Implementierung mit 3 Scheiben ausführen, erhalten wir folgende Ausgabe:
Scheibe 1 von A nach C verschoben
Scheibe 2 von A nach B verschoben
Scheibe 1 von C nach B verschoben
Scheibe 3 von A nach C verschoben
Scheibe 1 von B nach A verschoben
Scheibe 2 von B nach C verschoben
Scheibe 1 von A nach C verschoben
Fazit
Der Turm von Hanoi ist ein klassisches Rätselspiel, das sich hervorragend zur Veranschaulichung von Rekursion in der Informatik eignet. Die Java-Implementierung zeigt, wie der rekursive Algorithmus in Code umgesetzt werden kann.
Auch wenn das Rätsel nur aus Scheiben besteht, die sich auf Stäben befinden, kann es auf eine Vielzahl realer Probleme angewendet werden, bei denen es darum geht, Objekte in eine bestimmte Reihenfolge zu bringen.
FAQs
1. Was ist der Turm von Hanoi?
Der Turm von Hanoi ist ein klassisches Rätselspiel, bei dem es darum geht, Scheiben von einem Stab auf einen anderen zu verschieben, wobei gewisse Regeln beachtet werden müssen.
2. Was ist Rekursion?
Rekursion ist eine Programmiertechnik, bei der eine Funktion sich selbst aufruft, um komplexe Probleme in kleinere Teilprobleme aufzuteilen.
3. Wie lautet der Algorithmus für den Turm von Hanoi?
Der Algorithmus für den Turm von Hanoi ist rekursiv und kann wie folgt beschrieben werden:
* Wenn nur eine Scheibe vorhanden ist, verschiebe sie auf den Zielstab.
* Andernfalls:
* Verschiebe die oberste Scheibe vom Quellstab auf den Zwischenstab.
* Rufe den Algorithmus rekursiv auf, um den verbleibenden Turm von der Quelle zum Ziel zu verschieben.
* Rufe den Algorithmus rekursiv auf, um die einzelne Scheibe vom Zwischenstab zum Ziel zu verschieben.
4. Wie kann der Turm von Hanoi in Java implementiert werden?
Der Turm von Hanoi kann in Java rekursiv implementiert werden, indem eine Methode erstellt wird, die den Algorithmus aufruft.
5. Wie hoch ist die Komplexität des Algorithmus für den Turm von Hanoi?
Die Komplexität des Algorithmus für den Turm von Hanoi beträgt O(2^n), wobei n die Anzahl der Scheiben ist.
6. Welche realen Probleme können mit dem Turm von Hanoi gelöst werden?
Der Turm von Hanoi kann zur Lösung einer Vielzahl realer Probleme verwendet werden, bei denen es darum geht, Objekte in eine bestimmte Reihenfolge zu bringen, z. B. beim Sortieren von Daten oder beim Ausführen von Suchvorgängen.
7. Wie kann ich den Turm von Hanoi online spielen?
Es gibt viele Websites und Apps, auf denen du den Turm von Hanoi online spielen kannst, z. B. Mathsisfun.com.
8. Wo kann ich mehr über den Turm von Hanoi erfahren?
Es gibt viele Ressourcen im Internet, die mehr Informationen über den Turm von Hanoi bieten, z. B. Wikipedia oder Khan Academy.