%% -*- mode: latex; TeX-master: "informatik.tex"; -*-

\begin{slide}{Schwere Probleme}

\kopf{$ $Id: hanoi.tex,v 1.1 2006-10-09 13:24:19 waldmann 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 \emph{nie} eine größere über einer kleineren Scheibe liegen.
Es darf \emph{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! 
\end{slide}

\begin{slide}{Hanoi (2)}

Also ist das die optimale Lösung:
\begin{verbatim}
move (k, v, n, h) =
    -- hier gilt: Scheiben 1, 2 .. k 
    -- liegen oben auf v (andere Scheiben egal)
    falls (k > 0), dann
        move (k-1, von, hilf, nach)
        lege Scheibe k von v nach n
        move (k-1, hilf, von, nach)
    -- hier gilt: Scheiben 1, 2 .. k 
    -  liegen oben auf n
    --     (andere Scheiben wurden nicht bewegt)
\end{verbatim}
und für $k$ Scheiben braucht man $2^k-1$ Züge.

\[
\begin{array}{c|cccccccc}
n    & 5 & 10 & 15 & 20 & 25 & 30 & 50 & 100 \\ \hline
H(n) & 31 & 1023 & 10^4 & 10^6 & 10^7 & 10^9 & 10^{15} & 10^{30}
\end{array}
\]

\end{slide}
