Wieże Hanoi to jedno z tych zadań, które wyglądają niewinnie, a po chwili pokazują, jak szybko rośnie złożoność prostych reguł. W tym tekście rozbijam układankę na jasne części: wyjaśniam klasyczne zasady, pokazuję, skąd bierze się wzór 2^n - 1, i podaję konkretne przykłady dla kilku liczby krążków. Dorzucam też praktyczne skróty, dzięki którym łatwo sprawdzisz wynik bez rozpisywania całej sekwencji ruchów.
Najkrótsza odpowiedź jest prosta, ale liczba ruchów rośnie błyskawicznie
- W klasycznej wersji z trzema słupkami minimalna liczba ruchów to 2^n - 1.
- Dla 3 krążków potrzeba 7 ruchów, dla 4 krążków 15, a dla 10 krążków już 1023.
- Każdy kolejny krążek niemal podwaja trudność zadania.
- Najwygodniej liczyć to rekurencyjnie: najpierw przenieść mniejszą wieżę, potem największy krążek, a na końcu znów mniejszą wieżę.
- Wzór dotyczy klasycznych Wież Hanoi z trzema słupkami; w wariantach z większą liczbą słupków sytuacja robi się bardziej złożona.
Jak działa klasyczna wersja wież Hanoi
Najpierw warto odciąć się od legend i od razu przejść do sedna. W klasycznej wersji mam trzy słupki, na jednym stoi wieża z n krążków ułożonych od największego na dole do najmniejszego na górze, a celem jest przeniesienie całej wieży na inny słupek. Mogę ruszyć tylko jeden krążek naraz i nie wolno położyć większego na mniejszym.
To brzmi banalnie, ale właśnie te dwa ograniczenia tworzą całą trudność. Nie da się po prostu „przerzucić” największego elementu od razu, bo najpierw trzeba odsunąć wszystko, co leży nad nim. Dlatego w praktyce każda poprawna strategia obraca się wokół tego samego schematu: najpierw przenoszę mniejszą wieżę, potem największy krążek, a na końcu znów mniejszą wieżę. To prowadzi bezpośrednio do wzoru, który zaraz rozpiszę krok po kroku.
Skąd bierze się wzór 2^n - 1
Jeśli mam wyjaśnić to bez nadmiaru matematyki, zaczynam od jednego faktu: żeby ruszyć największy krążek, muszę najpierw przenieść n - 1 mniejszych na słupek pomocniczy. Potem wykonuję jeden ruch z największym krążkiem, a następnie znowu przenoszę te n - 1 krążków na cel. Z tego od razu wychodzi zależność:
M(n) = 2M(n - 1) + 1, gdzie M(0) = 0 albo, w praktyce szkolnej, startujemy od najprostszego przypadku M(1) = 1.
Ta rekurencja oznacza dokładnie tyle: liczba ruchów dla wieży z n krążków to dwa razy liczba ruchów dla wieży z n - 1 krążków, plus jeden ruch na największy krążek. Z takiego ciągu bardzo szybko wychodzi wzór 2^n - 1. To właśnie ten wynik podaje też NIST jako minimum dla klasycznej wersji problemu.
Najprostszy sposób, by to poczuć, to spojrzeć na kolejne wartości: 1, 3, 7, 15, 31, 63. Każda z nich jest o jeden mniejsza od kolejnej potęgi dwójki. I to nie jest przypadek, tylko dokładnie ten sam mechanizm zapisany w innej formie. Dzięki temu możemy przejść od dowodu do liczb, które da się od razu wykorzystać w praktyce.
Ile ruchów wychodzi dla najczęstszych przypadków
W zadaniach i quizach ludzie najczęściej pytają nie o sam wzór, tylko o konkretny wynik. Dlatego najwygodniej zapamiętać kilka pierwszych wartości i od razu widzieć, jak szybko rośnie liczba ruchów.
| Liczba krążków | Minimalna liczba ruchów | Co to oznacza w praktyce |
|---|---|---|
| 1 | 1 | Jeden prosty ruch, bez kombinowania. |
| 2 | 3 | Już trzeba chwilowo odsunąć mniejszy krążek. |
| 3 | 7 | Pojawia się wyraźny rytm ruchów. |
| 4 | 15 | Trudność prawie się podwaja w porównaniu z 3 krążkami. |
| 5 | 31 | Wciąż mało elementów, a ruchów robi się wyraźnie więcej. |
| 10 | 1023 | Tu już bardzo dobrze widać wzrost wykładniczy. |
Jeśli chcesz szybki punkt odniesienia, zapamiętaj prostą sekwencję: 1, 3, 7, 15, 31, 63. To praktycznie wszystko, co trzeba wiedzieć, by bezbłędnie odpowiedzieć na typowe pytanie o minimalną liczbę ruchów. Z tej listy płynnie przechodzę do pytania, jak takie wyniki liczyć bez rozpisywania całej ścieżki ruchów.
Jak policzyć wynik bez rozpisywania wszystkich kroków
W codziennej pracy, zwłaszcza jeśli liczę to „na szybko”, używam jednej prostej zasady: podnieś 2 do potęgi n i odejmij 1. Dla 8 krążków wychodzi więc 255, bo 2^8 = 256. Dla 10 krążków dostaję 1023, bo 2^10 = 1024.
W praktyce można to zrobić na trzy sposoby:
- na kalkulatorze, gdy liczba krążków jest większa niż kilka;
- z pamięci, jeśli kojarzysz kolejne potęgi dwójki;
- rekurencyjnie, gdy chcesz zrozumieć sam mechanizm, a nie tylko dostać liczbę.
Ja zwykle polecam myślenie rekurencyjne, bo ono najlepiej tłumaczy, dlaczego wzór działa. Z kolei do szybkich zadań wystarczy czysta arytmetyka: jeśli widzisz liczbę krążków, liczysz potęgę dwójki i odejmujesz jeden. To także najwygodniejszy sposób, by sprawdzić się w grach logicznych albo podczas konkursowych zadań na czas.
W materiałach ZPE rozwiązanie iteracyjne pokazuje nawet praktyczny rytm ruchów: najmniejszy krążek porusza się naprzemiennie, a między jego ruchami wykonuje się jedyny możliwy ruch innym krążkiem. To dobry test, jeśli chcesz nie tylko znać wynik, ale też umieć dojść do niego bez zgadywania. Po takim skrócie najłatwiej zobaczyć, gdzie ludzie najczęściej mylą się w obliczeniach.
Najczęstsze błędy przy liczeniu ruchów
Największy błąd to mylenie tej zagadki z liniowym liczeniem kroków. Intuicja podpowiada czasem: „dołożę jeden krążek, to będzie trochę więcej ruchów”, ale tutaj to nie działa w sposób łagodny. Każdy dodatkowy krążek uruchamia podwojenie poprzedniego wyniku, więc wzrost jest wykładniczy, a nie liniowy.
Drugi częsty błąd to pomijanie warunku, że największy krążek można ruszyć dopiero wtedy, gdy znikną wszystkie mniejsze. Z tego właśnie wynika konieczność przenoszenia całej mniejszej wieży dwa razy. Gdy ktoś tego nie zauważy, łatwo zaniża wynik albo próbuje „skracać” ruchy w sposób niezgodny z zasadami.
Warto też uważać na liczbę słupków. Klasyczne wzory 2^n - 1 dotyczą wersji z trzema słupkami. Jeśli do zabawy dołożysz dodatkowy słupek, optymalny wynik już nie musi wyglądać tak samo. To pozorny detal, ale w praktyce całkowicie zmienia zadanie. I właśnie dlatego ostatnia rzecz, którą warto zapamiętać, dotyczy granic samego wzoru.
Kiedy ten wzór przestaje wystarczać
2^n - 1 to wzór dla klasycznych Wież Hanoi z trzema słupkami. Jeśli zmienisz warunki i dasz graczowi cztery lub więcej słupków, pojawia się inna klasa problemów, a minimum ruchów nie da się już opisać tak prostą regułą. To ważne rozróżnienie, bo w sieci łatwo pomylić klasyczną zagadkę z jej wariantami i wyciągnąć zły wniosek.
To także dobry moment, by spojrzeć na samą skalę trudności. Dla 10 krążków 1023 ruchy nadal da się ogarnąć w głowie, ale dla 20 krążków robi się już ponad milion ruchów, a dla 64 krążków liczba rośnie do poziomu, którego nie da się sensownie „przeczekać” ani wykonać ręcznie. Właśnie dlatego Wieże Hanoi są tak dobrym przykładem złożoności wykładniczej: mała zmiana wejścia daje ogromny skok wyniku.
Jeśli mam zostawić jedną rzecz do zapamiętania, to tę: w klasycznej wersji nie szukasz sprytnego skrótu, tylko rozpoznajesz wzór, który od początku wymusza konkretną liczbę ruchów. Dla trzech słupków odpowiedź jest zawsze ta sama i bardzo łatwa do sprawdzenia: 2^n - 1, czyli wynik, który szybko rośnie razem z liczbą krążków.
