Wieże Hanoi i myślenie rekurencyjne

Jak rozwiązać wieże Hanoi, ile ruchów potrzeba (2ⁿ − 1) i na czym polega myślenie rekurencyjne: duży problem to mały problem plus jeden ruch.

Łamigłówki i gry logiczneKlasy 3–8

Wieże Hanoi to łamigłówka z trzema słupkami i kilkoma krążkami o różnych rozmiarach. Na początku wszystkie krążki leżą na pierwszym słupku jak wieża, największy na dole. Zadanie: przenieść całą wieżę na trzeci słupek. Wolno przenosić jeden krążek naraz i nigdy nie wolno położyć większego krążka na mniejszym.

Według legendy, która towarzyszyła zabawce sprzedawanej w XIX wieku, mnisi w świątyni przekładają 64 złote krążki, a gdy skończą, nastąpi koniec świata. Zagadkę sprowadził do Europy francuski matematyk Édouard Lucas w 1883 roku. Czy trzeba się bać? Zaraz to policzymy.

Zacznijmy od małych wież

  • 1 krążek: przenosimy go prosto na cel. To 1 ruch.
  • 2 krążki: mały na słupek pomocniczy, duży na cel, mały na duży. To 3 ruchy.
  • 3 krążki: kombinacja, którą zobaczysz w animacji poniżej. To 7 ruchów.

Myślenie rekurencyjne

Zauważ, co dzieje się w animacji. Aby przenieść największy krążek (3), musiałeś najpierw zdjąć z niego dwa mniejsze, czyli przenieść wieżę z 2 krążków na słupek pomocniczy. Potem jeden ruch dużego krążka, a na koniec znów przenieść wieżę z 2 krążków, tym razem na cel. Wieża z 3 krążków to dwie wieże z 2 krążków plus jeden ruch.

RekurencjaRozwiązanie problemu o rozmiarze n polega na dwukrotnym rozwiązaniu tego samego problemu o rozmiarze n − 1 i wykonaniu jednego dodatkowego kroku. Kończymy, gdy rozmiar to 1 lub 0, bo wtedy odpowiedź jest oczywista.

Ten sposób myślenia przydaje się daleko poza łamigłówkami. Wielka matrioszka zawiera mniejszą matrioszkę, która zawiera jeszcze mniejszą. Aby je policzyć, wystarczy otworzyć największą i policzyć resztę, a resztę liczymy tak samo.

Ile ruchów potrzeba?

Niech R(n) oznacza liczbę ruchów dla n krążków. Z rozumowania wyżej: R(n) = R(n − 1) + 1 + R(n − 1) = 2 · R(n − 1) + 1. Zaczynamy od R(1) = 1 i liczymy:

  • R(2) = 2 · 1 + 1 = 3,
  • R(3) = 2 · 3 + 1 = 7,
  • R(4) = 2 · 7 + 1 = 15,
  • R(5) = 2 · 15 + 1 = 31,
  • R(6) = 2 · 31 + 1 = 63.

Liczby 1, 3, 7, 15, 31, 63 to potęgi dwójki zmniejszone o 1: 2¹ − 1, 2² − 1, 2³ − 1… Zatem dla n krążków minimum to 2ⁿ − 1 ruchów. Każdy dodatkowy krążek podwaja pracę.

A te 64 krążki?Potrzeba 2⁶⁴ − 1 = 18 446 744 073 709 551 615 ruchów. Przy jednym ruchu na sekundę zajęłoby to około 584,6 miliarda lat, czyli znacznie więcej niż wiek Wszechświata. Koniec świata nam nie grozi.

Rekurencja także gdzie indziej

Silnię liczby zapisujemy tak samo: 5! = 5 · 4!, a 4! = 4 · 3!, i tak dalej, aż dojdziemy do 1! = 1. Wynik 5! = 120 składa się z kolejnych mniejszych wyników. Taki zapis jest krótki, bo każdy krok wygląda identycznie. Ćwicz zawsze dwie rzeczy: jak sprowadzić problem do mniejszego i kiedy się zatrzymać. Gdybyś pominął drugą część, rozumowanie nigdy by się nie skończyło.

Prosty wzorzec dla ręki

Najmniejszy krążek porusza się co drugi ruch. Jeśli wieża ma nieparzystą liczbę krążków (np. 3), najmniejszy krążek wędruje cyklicznie A → C → B → A… Jeśli parzystą (np. 2 lub 4), wędruje A → B → C → A… W pozostałych ruchach jest tylko jeden dozwolony ruch innym krążkiem, więc nie musisz niczego wymyślać. Wystarczy pilnować tego rytmu.

Zadania

1. Ile ruchów wymaga wieża z 5 krążków? A z 7?

Pokaż rozwiązanie
2⁵ − 1 = 32 − 1 = 31. 2⁷ − 1 = 128 − 1 = 127.

2. Wypisz ruchy dla wieży z 2 krążków (A – start, B – pomocniczy, C – cel). Krążki: 1 (mały), 2 (duży).

Pokaż rozwiązanie
Ruch 1: krążek 1 z A na B. Ruch 2: krążek 2 z A na C. Ruch 3: krążek 1 z B na C. Razem 3 ruchy.

3. Przy jednym ruchu na sekundę ile czasu zajmie wieża z 7 krążków?

Pokaż rozwiązanie
127 ruchów, czyli 127 sekund. To 2 minuty i 7 sekund (127 = 2 · 60 + 7).

4. Wieża z 10 krążków ma 1023 ruchów. Ile ruchów ma wieża z 11 krążków?

Pokaż rozwiązanie
R(11) = 2 · 1023 + 1 = 2047. Sprawdź wzorem: 2¹¹ − 1 = 2048 − 1 = 2047.

Typowe błędy

  • Przenoszenie największego krążka zbyt wcześnie, gdy mniejsze jeszcze na nim leżą.
  • Zbędne ruchy, które wydłużają rozwiązanie ponad minimum.
  • Zgadywanie wzoru bez sprawdzenia: 2ⁿ − 1, nie 2ⁿ.

Zapamiętaj

  • Minimalna liczba ruchów dla n krążków to 2ⁿ − 1.
  • Duży problem to dwa razy mniejszy problem plus jeden ruch.
  • Każdy nowy krążek podwaja liczbę ruchów.
  • Najmniejszy krążek rusza się co drugi ruch.

Spróbuj samodzielnie w grze Wieże Hanoi. Licznik pokaże Ci, ile ruchów to minimum.

Zagraj w temacie

Komentarze

Dodaj komentarz

Komentarz pojawi się po zatwierdzeniu. Adres e-mail nie będzie widoczny. Nie podawaj danych osobowych dziecka.