Turm von Hanoi
(Turm von Benares)
Problem:
Verlege einen Turm, der aus n unterschiedlich großen Scheiben besteht, vom Startplatz zum Zielplatz.
Regeln:
1 Es steht ein Hilfslagerplatz zur Verfügung.
2 Es darf in jedem Zug nur eine Scheibe bewegt werden.
3 Es darf niemals eine größere Scheibe auf eine kleinere Scheibe gelegt werden.
Lösung:
Um einen Turm aus n Scheiben vom Startplatz zum Zielplatz zu bewegen sind folgende Schritte notwendig:
1 Bewege n-1 Scheiben vom Startplatz zum Hilfslagerplatz. Benutze den Zielplatz als Lager.
2 Bewege die unterste Scheibe vom Startplatz zum Zielplatz.
3 Bewege n-1 Scheiben vom Hilfslagerplatz zum Zielplatz. Benutze den Startplatz als Lager.
4 Wende die Schritte 1 bis 3 rekursiv auf alle Türme, die aus mehr als einer Scheibe bestehen, an!
Das Problem Turm von Hanoi hat eine exponentielle Zeitabhängigkeit. Mit jeder neu hinzukommenden Scheibe verdoppelt sich in etwa die benötigte Zeit.
Für einen Turm, der aus n Scheiben besteht, benötigt man (2 hoch n)-1 Züge.
Quelltext der Applikation
public class Turm_von_Hanoi
{
static int zug;
/* Globale Variable, zaehlt die Anzahl der benoetigten Zuege. */
static void turm(int anzahl, char vonturm, char nachturm, char lager)
{
if (anzahl>0)
/* Austrittsbedingung fuer die Rekursion */
{
turm(anzahl-1,vonturm,lager,nachturm);
/* Schritt 1 - rekursiver Aufruf */
System.out.print("Scheibe "+anzahl);
System.out.print(" von "+vonturm);
System.out.println(" nach "+nachturm);
/* Schritt 2 */
zug=zug+1;
turm(anzahl-1,lager,nachturm,vonturm);
/* Schritt 3 */
}
}
public static void main(String args[])
{
int scheiben;
char quelle='A', ziel='B', hilfe='C';
System.out.println("Bitte geben Sie die Anzahl der Scheiben, ");
System.out.print("aus denen der Turm besteht, an:");
scheiben=In.readInt();
if (scheiben<=0)
System.out.println("Regeln beachten!");
else
turm(scheiben,quelle,ziel,hilfe);
System.out.println();
System.out.println();
System.out.println("Das waren " + zug + " Zuege");
}
}
Anmerkung
Der Sage nach befinden sich im Hindu-Tempel von Benares drei Stifte mit 64 goldenen Lochscheiben unterschiedlicher Größe.
Gott Brahma hat bei der Erschaffung der Erde alle Scheiben zu einer Pyramide, auf einem Stift geformt, übergeben. Die Hindu-Priester erhielten den Auftrag, diese Scheiben einzeln auf einen der beiden Stifte zu setzen, wobei niemals eine größere auf eine kleinere Scheibe gesetzt
werden durfte.
In dem Moment, wo die Pyramide über einem anderen Stift neu errichtet ist, würde die Welt untergehen.
Wie lange brauchen die Priester, wenn sie pro Sekunde einen Zug machen?
Vergleichen Sie diese Zeit mit dem Alter unserer Sonne (etwa 5 Mrd. Jahre)!