Turm von Hanoi

Eine interaktive Übung zum Anwenden des rekursiven Algorithmus. Startturm, Hilfsturm und Zielturm können vor dem ersten Zug mit der Maus festgelegt werden.

1. Grundidee des Algorithmus

Regeln

  1. Es darf immer nur eine Scheibe bewegt werden.
  2. Es darf nur die oberste Scheibe eines Turms genommen werden.
  3. Eine größere Scheibe darf nie auf einer kleineren liegen.

Rekursiver Lösungsplan

Um n Scheiben vom Startturm zum Zielturm zu bewegen, benutzt man den Hilfsturm:

  1. Bewege n−1 Scheiben vom Startturm zum Hilfsturm.
  2. Bewege die größte Scheibe vom Startturm zum Zielturm.
  3. Bewege n−1 Scheiben vom Hilfsturm zum Zielturm.

Wichtig: Der Algorithmus bleibt gleich, auch wenn Start, Hilfe und Ziel vertauscht werden. Nur die Namen der Türme ändern sich.

hanoi(n, start, ziel, hilfe):
    wenn n == 1:
        bewege eine Scheibe von start nach ziel
    sonst:
        hanoi(n-1, start, hilfe, ziel)
        bewege eine Scheibe von start nach ziel
        hanoi(n-1, hilfe, ziel, start)

2. Interaktive Übung

Vor dem ersten Zug Rollen ändern: Klicke anschließend auf einen Turm.

Vor dem ersten Zug kannst du Start, Hilfe und Ziel ändern. Danach: erst Turm mit Scheibe, dann Zielturm anklicken.

3. Warum Rekursion hier passt

Die Aufgabe wirkt zuerst kompliziert. Der Trick ist, sie immer wieder auf eine kleinere Aufgabe zurückzuführen: Statt alle Scheiben auf einmal zu bewegen, betrachtet man zuerst den Turm aus n−1 Scheiben. Genau diese kleinere Aufgabe hat dieselbe Struktur wie die ursprüngliche Aufgabe.

Für n Scheiben braucht man bei optimaler Lösung immer 2n − 1 Züge.