Algorytm rozwiązujący Wieżę Hanoi o zadanej wysokości w optymalnej ilości ruchów, wykorzystując metodę binarną.
Metoda binarna polega na zapisaniu numeru wykonywanego ruchu w systemie binarnym i sprawdzaniu który bit (licząc od prawej stony) naszej liczby zmienił się z zera na 1.
Na przykład:
- W pierwszym ruchu zwiększa się pierwszy bit 0 >>> 1
- W drugim ruchu zwiększa się drugi bit 1 >>> 10
- W trzecim ruchu znowu zwiększa się pierwszy bit 10 >>> 11
Każdy bit odpowiada elementowi wieży. Licząc od prawej, pierwszy bit to najmniejszy element, drugi bit to drugi najmniejszy element i tak aż do największego elementu wieży.
Bit którego zmianę zaobserwowaliśmy sygnalizuje, który element wieży należy przenieść. Metoda binarna nigdy nie wskazuje elementu, którego przeniesienie byłoby w tym momencie ruchem nielegalnym. Jeżeli całkowita liczba elementów wieży jest parzysta, należy przenieść element na najbliższy stos po prawej, a jeżeli to niemożliwe to należy go przenieść o dwa stosy w prawo. Jeżeli całkowita liczba elementów jest nieparzysta, należy dany element przenieść na najbliższy stos po lewej, a jeżeli to niemożliwe to o dwa stosy w lewo.
Stos trzyelementowy
1
2
3
W pierwszym ruchu należy przenieść pierwszy element w lewo
2
3 1
W drugim ruchu należy przenieść drugi element w lewo, ale nie można go położyć na pierwszym elemencie, więc przenosimy go o dwa pola w lewo.
3 2 1
W trzecim ruchu znowu należy przenieść pierwszy element w lewo
1
3 2
W czwartym ruchu należy przenieść trzeci element
1
2 3
W piątym ruchu znowu należy przenieść pierwszy element w lewo
1 2 3
W szóstym ruchu należy przenieść drugi element w lewo, ale ponownie nie można go położyć na elemencie pierwszym, więc przenosimy go o dwa pola w lewo.
2
1 3
W ostatnim ruchu należy przenieść pierwszy element o jedno pole w lewo
1
2
3
Jest to optymalna liczba ruchów, wyrażona wzorem 2^n - 1
Analogicznie należy postępować z dowolną liczbą elementów, biorąc pod uwagę, czy jest to liczba parzysta, czy nieparzysta.
Program najpierw tworzy trzy Stosy (Stack), A, B, oraz C, po czym wypełnia stos A liczbą elementów zadaną przez użytkownika. Stos B oraz C na razie są pozostawione puste. Następnie program rysuje stos A, po czym czeka 100ms i wchodzi w pętlę, z której nie wyjdzie dopóki stos C nie będzie wyglądał tak samo, jak początkowy stos A.
Na początku pętli program sprawdza jaki ruch został wykonany poprzednio (na początku jest to 0), oraz jaki ruch zostanie wykonany następny. Liczby te zamienia na liczby binarne. Po czym porównuje który bit zmienił się z 0 na 1
Następnie sprawdzane jest to, czy liczba elementów jest parzysta, czy nieparzysta, oraz który Stos ma na szczycie element, który należy przenieść. Program sprawdza, na który ze stosów powinien przenieść dany element, po czym wykonuje ten ruch.
Na końcu pętli stosy są rysowane przez program, a stos C porównywany jest do początkowego stanu stosu A, jeżeli zostanie zwrócona wartość true, pętla jest przerywana, a program końćzy swoje działanie. Jeżeli zwrócona zostanie wartość false, program poczeka 100ms (aby użytkownik był w stanie obserwować zmiany) i pętla rozpocznie się na nowo.