Türme von Hanoi

 

In der Informatik gelten die Türme von Hanoi (Wiki) als ein Paradebeispiel für ein Problem, das sich nur rekursiv (oder iterativ) lösen lässt. Die Zeit für die Berechnung einer bestimmten Position n wächst also exponentiell mit O(2ⁿ). In diesem Artikel wird eine explizite Lösung vorgestellt, mit der man jede Position n mit der gleichen Rechenzeit O(1) berechnen kann. Diese explizite Lösung wird in allen Animationen verwendet:

 http://mikomma.de/hanoi/hanoi.htm