Türme von Hanoi

Angenommen, man hat einen Turm oder besser Stapel von 64 Scheiben. Die Scheiben unterscheiden sich im Durchmesser und haben eine Bohrung in der Mitte. Damit sind sie, die größte Scheibe unten, auf einen Stab gesteckt. Es gibt zwei weitere Stäbe. Die Aufgabenstellung besteht darin, alle Scheiben vom ersten auf den zweiten Stab zu bewegen, wobei nur der dritte Stab als Ablage verwendet werden darf und nie eine größere über einer kleineren Scheibe liegen darf.

Der Legende nach sind die Scheiben aus Gold und befinden sich in einem asiatischen Tempel. Dort werden sie von Mönchen nach den oben beschriebenen Regeln bewegt. Sobald die Mönche ihre Aufgabe abgeschlossen haben und sich alle Scheiben auf dem zweiten Stab befinden, wird die Welt zu Staub zerfallen.

Die Aufgabenstellung lässt sich mittels Rekursion nach dem folgenden Algorithmus lösen:

- Um n > 1 Scheiben von A nach B zu bewegen, bewege (n - 1) Scheiben von A nach C, dann eine Scheibe, das ist die Größte, von A nach B und dann bewege (n - 1) Scheiben von C nach B.

- Eine Scheibe kann ohne Umstände von A nach B bewegt werden.

Das führt zu der folgenden rekursiven Funktion:

(defproc hanoi (n src dest help)
  (cond
    ((or (not (integer? n))
         (< n 0))
      (throw (quote error) "first argument must be a natural number"))
    ((= n 0)
      nil)
    ((= n 1)
     (list (list src dest)))
    (t
      (append
        (hanoi (- n 1) src help dest)
        (list (list src dest))
        (hanoi (- n 1) help dest src)))))

Für fünf Scheiben hat das Ergebnis 31 Schritte:

((a b) (a c) (b c) (a b) (c a) (c b) (a b) (a c) (b c) (b a)
 (c a) (b c) (a b) (a c) (b c) (a b) (c a) (c b) (a b) (c a)
 (b c) (b a) (c a) (c b) (a b) (a c) (b c) (a b) (c a) (c b)
 (a b))

Das Ergebnis für 64 Scheiben ist zu groß, um es hier darzustellen ohne dass diese Website zu Staub zerfällt.


hanoi.sheet.xml