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 bei Aufruf von

verlege (n, start, zwischen, ziel).

Offenbar:	$f(1)$	=	1
	$f(n)$	=	$f(n-1) + 1 +f(n-1)$	=	$2 \cdot f(n-1)+1$

d.h., die Wertetabelle beginnt wie folgt:

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

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

Beweis durch Induktion

Induktionsverankerung: $f(1) = 1 = 2^{1} - 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