Turm von Hanoi

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

1. Grundidee der Algorithmen

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.

Iterativer Lösungsplan

Man wiederholt immer drei Turmpaare. Zwischen dem angegebenen Paar macht man jeweils den einzigen erlaubten Zug.

  • Ungerade Scheibenzahl: Start ↔ Ziel, Start ↔ Hilfe, Hilfe ↔ Ziel
  • Gerade Scheibenzahl: Start ↔ Hilfe, Start ↔ Ziel, Hilfe ↔ Ziel

Wichtig: Beide Algorithmen bleiben 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. Rekursiv oder iterativ?

Die rekursive Lösung beschreibt die Aufgabe als kleinere Teilaufgabe: Erst n−1 Scheiben weglegen, dann die größte Scheibe bewegen, dann n−1 Scheiben wieder darauflegen.

Die iterative Lösung arbeitet dagegen mit einem festen Muster aus drei Turmpaaren. Das ist besonders gut geeignet, wenn man die Lösung Schritt für Schritt von Hand ausprobieren möchte.

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