PL 
EnglishDomyślny
Українська🗼 Wieże Hanoi — rekurencyjny solver i 2ⁿ−1 ruchów
Zobacz, jak wieże Hanoi rozwiązują się same optymalną rekurencją dla 1–10 krążków, z animacją podnieś-przenieś-połóż. Liczniki porównują ruchy z minimum 2ⁿ−1; przełącz na tryb ręczny i rozwiąż samodzielnie.
O Wieżach Hanoi
Wieże Hanoi to łamigłówka matematyczna wynaleziona przez francuskiego matematyka Édouarda Lucasa w 1883 roku. Zadanie polega na przeniesieniu stosu N krążków ze słupka źródłowego na słupek docelowy, używając trzeciego, pomocniczego słupka, przestrzegając zasady, że większy krążek nigdy nie może zostać położony na mniejszym. Optymalne rozwiązanie rekurencyjne osiąga to w dokładnie 2N − 1 ruchach, co jest dowiedlnie minimalne: każdą podwieżę N−1 krążków trzeba przenieść dwukrotnie (raz w celu jej zdjęcia i raz z powrotem na największy krążek), plus jeden ruch dla dolnego krążka. Dla N=64 krążków — legendarnego założenia łamigłówki — minimalna liczba ruchów przekracza 1,8 × 1019, wymagając miliardów lat przy jednym ruchu na sekundę.
Ta symulacja animuje rekurencyjne rozwiązanie dla 1–8 krążków, rysując każdy ruch krok po kroku z konfigurowalną prędkością. Obok słupków wyświetlane jest drzewo wywołań rekurencji, uwidaczniając strukturę dziel-i-zwyciężaj: każde wywołanie Hanoi(N) tworzy dwukrotnie Hanoi(N−1), ilustrując wykładniczy wzrost liczby ruchów.
Najczęściej zadawane pytania
Dlaczego Wieże Hanoi wymagają dokładnie 2N − 1 ruchów?
Przez indukcję: dla N=1 wystarczy jeden ruch (21−1=1). Dla N krążków musimy najpierw przenieść górne N−1 krążków na słupek pomocniczy (2N−1−1 ruchów), następnie przenieść największy krążek na cel (1 ruch), a następnie przenieść stos N−1 krążków na cel (2N−1−1 ruchów). Razem: 2·(2N−1−1)+1 = 2N−1. Argument dolnego ograniczenia pokazuje, że żadne rozwiązanie nie może użyć mniejszej liczby ruchów.
Jaki jest iteracyjny algorytm dla Wież Hanoi?
Elegancki algorytm iteracyjny na przemian stosuje dwie zasady: (1) wykonaj legalny ruch obejmujący najmniejszy krążek, oraz (2) wykonaj jedyny legalny ruch nieobejmujący najmniejszego krążka. Działa też interpretacja binarna: krążek przenoszony w kroku m to krążek na pozycji najniższego ustawionego bitu m. Wiąże to Wieże Hanoi bezpośrednio z liczeniem binarnym i enumeracją kodu Graya.
Jak Wieże Hanoi ilustrują rekurencję i dziel-i-zwyciężaj?
Trzyliniowe rozwiązanie rekurencyjne doskonale ilustruje dziel-i-zwyciężaj: rozłóż problem N krążków na dwa podproblemy rozmiaru N−1 i jeden przypadek bazowy (przenieś jeden krążek). Drzewo wywołań to pełne drzewo binarne o głębokości N z 2N−1 wywołaniami liściowymi (po jednym na ruch), co daje łącznie dokładnie 2N−1 pracy. Jest to kanoniczny przykład używany niemal w każdym wprowadzającym podręczniku algorytmów.
Czy istnieje wzór jawny na to, na którym słupku znajduje się krążek k po m ruchach?
Tak. Krążek k (indeksowany od 0, najmniejszy) znajduje się na słupku (bit k liczby m) XOR (bit k+1 liczby m) w standardowym kodowaniu trzysłupkowym, gdzie m jest wyrażone binarnie. Pozwala to na obliczenie dowolnego stanu w czasie O(log m) bez symulowania wszystkich poprzednich ruchów — użyteczna właściwość do weryfikacji dużych sekwencji Hanoi obliczeniowo lub implementacji szybkiego wyszukiwania stanu.
Czym jest hipoteza Frame'a-Stewarta dla czterech lub więcej słupków?
Przy czterech słupkach mniej niż 2N−1 ruchów może wystarczyć. Algorytm Frame'a-Stewarta (1941) zakłada, że optymalna liczba ruchów wynosi w przybliżeniu 2·√(2N) dla dużych N — wykładniczo lepiej niż przypadek trzech słupków. Hipoteza została udowodniona dla czterech słupków przez Bouscha w 2014 roku. Dla pięciu lub więcej słupków optymalna liczba pozostaje otwartym problemem kombinatoryki.
Ile czasu zajęłoby rozwiązanie Wież Hanoi z 64 krążkami?
Minimalna liczba ruchów dla 64 krążków wynosi 264−1 ≈ 1,84 × 1019. Przy jednym ruchu na sekundę zajęłoby to około 585 miliardów lat — mniej więcej 42 razy więcej niż obecny wiek Wszechświata. Lucas nawiązał do tego w 1883 roku, sugerując (żartobliwie), że mnisi kończący łamigłówkę zakończyliby świat.
Jak Wieże Hanoi wiążą się z liczeniem binarnym i sekwencją linijki?
Sekwencja numerów krążków przenoszonych w optymalnym rozwiązaniu to 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, … — znana jako sekwencja linijki lub linijka Sterna-Brocota. Krążek przenoszony w kroku m równa się największej potędze 2 dzielącej m (pozycji najniższego ustawionego bitu). Ta sekwencja jest izomorficzna z sekwencją pozycji bitów zmieniających się podczas liczenia binarnego od 0 do 2N−1.
Czy Wieże Hanoi można rozwiązać nierekurencyjnie z jawnym stosem?
Tak. Umieść krotki (n, źródło, cel, pomocniczy) na stosie. Zdejmij krotkę: jeśli n=1, wypisz ruch; w przeciwnym razie umieść trzy mniejsze krotki w odwrotnej kolejności. Eliminuje to narzut wywołań funkcji i daje tę samą sekwencję. Jednak nadal używa O(2N) wpisów stosu do przechowywania wszystkich oczekujących podproblemów, więc złożoność pamięciowa jest identyczna z podejściem rekurencyjnym.
Jak graf Hanoi wiąże się z trójkątem Sierpińskiego?
Graf Hanoi — z prawidłowymi konfiguracjami krążków jako wierzchołkami i legalnymi ruchami pojedynczego krążka jako krawędziami — jest izomorficzny z fraktalem trójkąta Sierpińskiego na poziomie N. 3N stanów problemu Hanoi z N krążkami tworzy samopodobny graf, w którym trzy kopie problemu N−1 są połączone w wierzchołkach narożnych. To powiązanie stanowi podstawę zastosowań w analizie fraktalnej i badaniach złożoności teoriografowej.
Czy Wieże Hanoi są wykorzystywane w testowaniu neuropsychologicznym?
Tak. Wieże Hanoi (i ich bliski krewny, Wieża Londynu) to standardowe zadania w ocenie neuropsychologicznej, służące do oceny funkcji wykonawczych, pamięci roboczej i zdolności planowania. Badania pokazują, że pacjenci z uszkodzeniem płata czołowego lub chorobą Parkinsona radzą sobie znacząco gorzej w zadaniach Hanoi z wieloma krążkami, co czyni je czułą sondą funkcji kory przedczołowej w badaniach klinicznych.