Schwere Probleme

$$Id: hanoi.tex,v 1.2 2003/10/24 13:16:42 joe Exp $$

Es gibt Aufgaben, deren Lösung exponentiell lang ist.

Beispiel: Türme von Hanoi. $n$ Scheiben mit Durchmessern $1,2,\ldots,n$ liegen übereinander auf einem Turm $A$ (in einem Kloster in Hanoi, jedenfalls der Sage nach). Sie sollen einzeln auf einen Turm $B$ bewegt werden, allerdings darf nie eine größere über einer kleineren Scheibe liegen. Es darf ein Hilfsturm $C$ benutzt werden.

Scheibe $n$ (die größte) muß sich irgendwann einmal bewegen (da sie anfangs auf $A$ liegt, aber schließlich auf $B$ sein muß). Im besten Fall bewegt sie sich genau einmal. Zu diesem Zeitpunkt müssen alle anderen Scheiben auf $C$ liegen! Wie kommen sie dorthin? Das ist eine (um eine Scheibe) verkleinerte Version der selben Aufgabe!