www.edunet.tychy.pl

WIEŻE HANOI

Łamigłówka Wieże Hanoi powstała prawdopodobnie w Azji w XIX w. lub wcześniej. Jest to przykład zadania, którego złożoność obliczeniowa wzrasta niezwykle szybko w miarę zwiększania liczby elementów wieży.

Jeśli przez x oznaczymy poszukiwaną liczbę przełożeń krążków, a przez n - liczbę samych krążków, to x = 2n - 1. Zatem przy 7 krążkach trzeba dokonać 127 przełożeń, pod warunkiem, że nie będzie pomyłki.

Łamigłówka polega na przełożeniu wszystkich krążków z wieży A na wieżę B przestrzegając zasady, że nie można położyć krążka większego na mniejszym oraz jednorazowo można przenieść tylko jeden krążek.

ABC