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. Scheiben mit Durchmessern liegen übereinander auf einem Turm (in einem Kloster in Hanoi, jedenfalls der Sage nach). Sie sollen einzeln auf einen Turm bewegt werden, allerdings darf nie eine größere über einer kleineren Scheibe liegen. Es darf ein Hilfsturm benutzt werden.
Scheibe (die größte) muß sich irgendwann einmal bewegen (da sie anfangs auf liegt, aber schließlich auf sein muß). Im besten Fall bewegt sie sich genau einmal. Zu diesem Zeitpunkt müssen alle anderen Scheiben auf liegen! Wie kommen sie dorthin? Das ist eine (um eine Scheibe) verkleinerte Version der selben Aufgabe!