prev up next

Previous: Fakultät, Potenzieren, Fibonacci, GGT Up: Rekursion Next: Komplexität, Verifikation, Terminierung

Türme von Hanoi

Source: Hanoi.java     JavaDoc: Hanoi.html     Applet:

Analyse der Größe der erzeugten Ausgabe:

Sei $f(n)$ die Anzahl der generierten Verlegebefehle für $ n $ Scheiben, d.h. bei Aufruf von

verlege (n, start, zwischen, ziel).

Da für $n>0$ zwei neue Aufrufe mit verkleinertem $ n $ sowie eine Druckzeile entstehen, gilt offenbar:


\begin{displaymath}
f(n) := \left\{ \begin{array}{ll}
0 & \mbox{ falls n$~=~$0}...
... 2\cdot f(n-1) + 1 & \mbox{ falls n$~>~$0}
\end{array} \right.
\end{displaymath}

d.h., die Wertetabelle beginnt wie folgt:

$ n $ $f(n)$
$0$ $0$
$1$ $1$
$2$ $3$
$3$ $7$
$4$ $15$
$5$ $31$
$6$ $63$
   

Verdacht: $f(n)= 2^{n} -1$

Beweis durch Induktion

Induktionsverankerung: $f(0) = 0 = 2^{0} - 1$

Induktionsschritt: Sei bis $n - 1$ bewiesen:

$f(n)$ = $2 \cdot f(n-1)+1$ = $2 \cdot (2^{n-1} -1) + 1$ = $2^{n}-2+1$ = $2^{n}-1$
  $\uparrow$ $\uparrow$
  Rekursionsgleichung Induktionsannahme


prev up next
Previous: Fakultät, Potenzieren, Fibonacci, GGT Up: Rekursion Next: Komplexität, Verifikation, Terminierung