Schlüsselwörter:
- Algorithmus
- Hanoi-Turm
- Rekursion
- Java-Implementierung
Einführung
Der Hanoi-Turm ist ein seit Generationen bekanntes Knobelspiel. Ziel ist es, einen Stapel von Scheiben von einem Start- zu einem Zielstab zu bewegen, wobei folgende Bedingungen gelten: Es darf jeweils nur eine Scheibe bewegt werden, und eine größere Scheibe darf nie auf einer kleineren liegen. Die Komplexität des Spiels steigt mit der Anzahl der Scheiben.
In der Informatik dient der Hanoi-Turm oft als Paradebeispiel für Rekursion. Rekursion ist eine Programmiertechnik, bei der eine Funktion sich selbst aufruft. Dadurch lassen sich komplexe Probleme in kleinere, leichter zu lösende Teilprobleme zerlegen.
Der Algorithmus
Der Lösungsalgorithmus für den Hanoi-Turm basiert auf dem Prinzip der Rekursion und kann folgendermaßen beschrieben werden:
- Falls nur eine Scheibe vorhanden ist, bewege diese zum Zielstab.
- Andernfalls:
- Verschiebe den obersten Scheibenturm vom Quell- auf den Hilfsstab.
- Wende den Algorithmus rekursiv an, um den verbleibenden Scheibenturm vom Quell- auf den Zielstab zu bewegen.
- Wende den Algorithmus rekursiv an, um die einzelnen Scheiben vom Hilfs- auf den Zielstab zu bewegen.
Java-Implementierung
Die nachfolgende Java-Implementierung zeigt, wie der rekursive Algorithmus in Programmcode übersetzt werden kann:
public class TowerOfHanoi {
// Anzahl der Scheiben
private int n;
/**
* Konstruktor
* @param n Anzahl der Scheiben
*/
public TowerOfHanoi(int n) {
this.n = n;
}
/**
* Löst das Hanoi-Turm-Problem
* @param source Quellstab
* @param destination Zielstab
* @param auxiliary Hilfsstab
*/
public void solve(String source, String destination, String auxiliary) {
if (n == 1) {
System.out.println("Scheibe 1 von " + source + " nach " + destination + " bewegt");
} else {
solve(source, auxiliary, destination);
System.out.println("Scheibe " + n + " von " + source + " nach " + destination + " bewegt");
solve(auxiliary, destination, source);
}
}
public static void main(String[] args) {
TowerOfHanoi towerOfHanoi = new TowerOfHanoi(3);
towerOfHanoi.solve("A", "C", "B");
}
}
Ausgabebeispiel
Bei der Ausführung mit drei Scheiben liefert das Programm diese Ausgabe:
Scheibe 1 von A nach C bewegt Scheibe 2 von A nach B bewegt Scheibe 1 von C nach B bewegt Scheibe 3 von A nach C bewegt Scheibe 1 von B nach A bewegt Scheibe 2 von B nach C bewegt Scheibe 1 von A nach C bewegt
Zusammenfassung
Der Hanoi-Turm ist nicht nur ein unterhaltsames Spiel, sondern auch ein hervorragendes Beispiel für Rekursion in der Informatik. Die Java-Implementierung veranschaulicht, wie ein rekursiver Algorithmus in Code umgesetzt werden kann. Obwohl es sich um ein abstraktes Problem mit Scheiben auf Stäben handelt, finden die dabei verwendeten Prinzipien auch in der Lösung vieler realer Probleme Anwendung, bei denen es um die Anordnung von Objekten in einer bestimmten Reihenfolge geht.
FAQ
-
Was ist der Hanoi-Turm?
Der Hanoi-Turm ist ein klassisches Rätselspiel, bei dem Scheiben von einem Stab zu einem anderen unter Beachtung bestimmter Regeln verschoben werden müssen.
-
Was bedeutet Rekursion?
Rekursion ist eine Methode der Programmierung, bei der eine Funktion sich selbst aufruft, um komplexe Aufgaben in kleinere, handhabbare Teilprobleme zu zerlegen.
-
Wie lautet der Algorithmus für den Hanoi-Turm?
Der Algorithmus für den Hanoi-Turm ist rekursiv und kann wie folgt beschrieben werden:
Wenn es nur eine Scheibe gibt, wird sie zum Zielstab verschoben.
Andernfalls:
* Verschiebe den obersten Scheibenturm vom Quellstab zum Hilfsstab.
* 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 Hilfsstab zum Ziel zu verschieben. -
Wie lässt sich der Hanoi-Turm in Java implementieren?
Der Hanoi-Turm kann in Java rekursiv durch eine Methode implementiert werden, die den beschriebenen Algorithmus ausführt.
-
Wie hoch ist die Zeitkomplexität des Hanoi-Turm-Algorithmus?
Die Zeitkomplexität des Hanoi-Turm-Algorithmus ist O(2^n), wobei n die Anzahl der Scheiben ist.
-
Welche praktischen Probleme können mithilfe des Hanoi-Turm-Algorithmus gelöst werden?
Die Prinzipien des Hanoi-Turms lassen sich auf eine Vielzahl realer Probleme übertragen, bei denen es um die Anordnung von Objekten in einer bestimmten Reihenfolge geht, wie beispielsweise bei der Datensortierung oder der Durchführung von Suchvorgängen.
-
Wo kann ich den Hanoi-Turm online spielen?
Es gibt zahlreiche Webseiten und Apps, die es ermöglichen, den Hanoi-Turm online zu spielen, z.B. Mathsisfun.com.
-
Wo finde ich weitere Informationen zum Hanoi-Turm?
Im Internet gibt es zahlreiche Informationsquellen zum Hanoi-Turm, z. B. Wikipedia oder Khan Academy.