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:

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

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