Przykład algorytmu rekurencyjnego
Wieża Hanoi jest przykładem algorytmu rekurencyjnego. 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.
Na czym to polega ta gra?
Otóż do dyspozycji mamy dowolna ilość krążków. Każdy krążek 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 (ilość patyczków również może być zwiększona).
Na pozostałych patyczkach (dwóch zewnętrznych) 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.Życzę udanej zabawy :)
Przykładowe strony z Wieżą Hanoi:
http://zylla.wipos.p.lodz.pl/games/hanoi5p.html
http://online.freeware.info.pl/hanoi.html
Anna Pomykała