Problem wież Hanoi

1. Czym jest problem wież Hanoi?

Wieże Hanoi to klasyczna łamigłówka matematyczna wymyślona w 1883 roku przez francuskiego matematyka Édouarda Lucasa.

Zasady:

Mamy 3 paliki (A, B, C)
Na paliku A jest n krążków różnej wielkości (od największego na dole do najmniejszego na górze)
Cel: Przenieść wszystkie krążki z A na C
Reguły:
Można przenosić tylko 1 krążek na raz
Można brać tylko górny krążek z palika
Większy krążek NIE MOŻE leżeć na mniejszym

Wizualizacja (3 krążki):

Stan początkowy:
    A         B         C
   |||        |         |
  |||||       |         |
 |||||||      |         |
---------  ---------  ---------

Cel:
    A         B         C
    |         |        |||
    |         |       |||||
    |         |      |||||||
---------  ---------  ---------

2. Rozwiązanie rekurencyjne

Kluczowa obserwacja:

Aby przenieść n krążków z A na C (używając B):

Przenieś (n-1) krążków z A na B (używając C)
Przenieś największy krążek z A na C
Przenieś (n-1) krążków z B na C (używając A)

2.1. Implementacja

Wynik:

Przenieś krążek z A na C
Przenieś krążek z A na B
Przenieś krążek z C na B
Przenieś krążek z A na C
Przenieś krążek z B na A
Przenieś krążek z B na C
Przenieś krążek z A na C

7 ruchów dla 3 krążków!

3. Wizualizacja kroków (n=3)

Stan początkowy:
    A         B         C
   |||        |         |
  |||||       |         |
 |||||||      |         |

Ruch 1: A → C
    A         B         C
    |         |        |||
  |||||       |         |
 |||||||      |         |

Ruch 2: A → B
    A         B         C
    |        |||       |||
    |         |         |
 |||||||      |         |

Ruch 3: C → B
    A         B         C
    |        |||        |
    |       |||||       |
 |||||||      |         |

Ruch 4: A → C
    A         B         C
    |        |||        |
    |       |||||       |
    |         |      |||||||

Ruch 5: B → A
    A         B         C
   |||        |         |
    |       |||||       |
    |         |      |||||||

Ruch 6: B → C
    A         B         C
   |||        |        |||||
    |         |         |
    |         |      |||||||

Ruch 7: A → C (KONIEC!)
    A         B         C
    |         |        |||
    |         |       |||||
    |         |      |||||||

4. Liczba ruchów

Wzór:

Minimalna liczba ruchów = 2^n - 1

n (krążków)	Ruchy	Czas (1 ruch/s)
1	1	1 sekunda
2	3	3 sekundy
3	7	7 sekund
4	15	15 sekund
5	31	31 sekund
10	1,023	~17 minut
20	1,048,575	~12 dni
64	2^64 - 1	~585 mld lat

Dowód (indukcja):

Niech T(n) = liczba ruchów dla n krążków

T(1) = 1  (przypadek bazowy)

T(n) = T(n-1) + 1 + T(n-1)
     = 2×T(n-1) + 1

T(2) = 2×T(1) + 1 = 2×1 + 1 = 3
T(3) = 2×T(2) + 1 = 2×3 + 1 = 7
T(4) = 2×T(3) + 1 = 2×7 + 1 = 15

Ogólnie: T(n) = 2^n - 1

5. Implementacja z licznikiem

6. Implementacja ze stosami

7. Analiza złożoności

Złożoność czasowa: O(2^n)

Wynik:

n=1: 1 wywołań, 1 ruchów
n=2: 3 wywołań, 3 ruchów
n=3: 7 wywołań, 7 ruchów
n=4: 15 wywołań, 15 ruchów
n=5: 31 wywołań, 31 ruchów
...

Liczba wywołań = liczba ruchów = 2^n - 1

Złożoność pamięciowa: O(n)

Głębokość rekurencji = n (stos wywołań)

8. Wariant iteracyjny (bez rekurencji)

Możliwe, ale znacznie bardziej skomplikowane:

Wniosek: Rekurencja jest znacznie prostsza!

9. Warianty problemu

9.1. Wieże Hanoi z 4 palikami (Reve's puzzle)

Minimalna liczba ruchów: nie ma prostej formuły!

9.2. Ograniczenia na ruchy

Niektóre warianty zabraniają ruchów między konkretnymi palikami (np. A → C bezpośrednio).

10. Zastosowania praktyczne

10.1. Backup rotacyjny

Trzy poziomy backupów (dzienny, tygodniowy, miesięczny) – podobnie do wież Hanoi.

10.2. Algorytmy sortowania

Merge sort i quick sort używają podobnego podejścia "dziel i zwyciężaj".

10.3. Struktura danych

Implementacja niektórych struktur drzewiastych.

10.4. Gry i łamigłówki

Podstawa wielu gier logicznych.

11. Legenda o Wieżach Hanoi

Legenda: W świątyni w Benares (Indie) mnisi przenoszą 64 złote krążki na diamentowych palikach. Gdy skończą – nastąpi koniec świata!

Ile to potrwa?

Wynik:

Ruchy: 18,446,744,073,709,551,615
Lat: 584,942,417,355
Wiek wszechświata: ~13.8 miliardów lat

Wniosek: Ludzkość jest bezpieczna przez ~585 miliardów lat! 😄

12. Ćwiczenia

Zadanie 1: Zlicz ruchy bez wypisywania

Rozwiązanie

Zadanie 2: Która krążek porusza się w ruchu i?

13. Podsumowanie

Wieże Hanoi:

Klasyczny problem rekurencyjny
Minimalna liczba ruchów: 2^n - 1
Złożoność czasowa: O(2^n)
Złożoność pamięciowa: O(n) (stos wywołań)

Kluczowa idea:

Przenieś (n-1) krążków na palik pomocniczy
Przenieś największy krążek na cel
Przenieś (n-1) krążków z pomocniczego na cel

Rekurencja vs iteracja:

Rekurencja: elegancka, naturalna
Iteracja: możliwa, ale skomplikowana

Dlaczego to ważne:

Wzorzec "dziel i zwyciężaj"
Ilustracja wykładniczej złożoności
Fundament dla merge sort, quick sort
Doskonały przykład piękna rekurencji

Najważniejsza lekcja:

Niektóre problemy są naturalnie rekurencyjne. Wieże Hanoi to perfekcyjny przykład!

Co dalej warto poznać:

Algorytmy "dziel i zwyciężaj"
Merge sort, quick sort
Backtracking
Programowanie dynamiczne