• Wieża Hanoi

          • 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