Przykład algorytmu rekurencyjnego
Wieża Hanoi
Gra komputerowa dla każdego
Wieża Hanoi jest klasycznym przykładem rekurencji.
Jest ciekawą zagadką z algorytmiki i dlatego warto poświęcić jej chwilę uwagi.
Zagadka ta stała się znana dzięki matematykowi Eduardowi Lucasowi,
który wymyślił ją w XIX wieku i zastosował dla ośmiu krążków.
Wyjaśnijmy, na czym to polega.
Otóż mamy do dyspozycji n krążków.
Każdy z nich jest mniejszy od drugiego.
W krążkach wywiercono otwór dzięki któremu każdy z nich jest nałożony na jeden z trzech patyczków jakie posiadamy.
Na pozostałych patyczkach nie umieszczono na razie żadnych krążków.
Zadanie polega na przeniesieniu wszystkich krążków z jednego patyczka na drugi przy użyciu patyczka trzeciego.
Postawione są jednak pewne warunki:
– możemy przenosić krążki wyłącznie pojedynczo,
– w żadnym momencie krążek większy nie może leżeć na krążku mniejszym.