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 . 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ⁿ - 1

Beweis durch Induktion

Induktionsverankerung: f (1) = 1 = 2¹ - 1

Induktionsschritt: Sei bis n - 1 bewiesen:

f (n)	= 2 . f (n - 1) + 1	= 2 . (2n - 1 - 1) + 1 = 2n - 2 + 1 = 2n - 1
	Rekursionsgleichung	Induktionsannahme