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 · (2^{n - 1} - 1) + 1 = 2ⁿ - 2 + 1 = 2ⁿ - 1

Rekursionsgleichung Induktionsannahme