inthink.guide
SklepWróć na stronę główną

Graj. Przewiduj. Rozumiej.

Wieże Hanoi

Graj z 3–5 krążkami, proś o wskazówkę dla bieżącego układu i poznaj strategię rekurencyjną w dwóch krótkich animacjach. Otwórz przykład krok po kroku w dowolnej chwili.

Graj w Wieże Hanoi
ABCKrążek 44Krążek 33Krążek 22Krążek 11

Odsuń mały stos, aby uwolnić największy krążek.

Zasady Wież Hanoi

  1. Przenieś cały stos z pręta A na C.
  2. Przenoś po jednym krążku, zawsze z wierzchu.
  3. Nie kładź większego krążka na mniejszym.

Graj w Wieże Hanoi

Wybierz pręt początkowy, potem docelowy. Numery oznaczają rozmiar: 1 jest najmniejszy. Cofnij ruch lub zacznij od nowa.

Ruchy: 0
ABCKrążek 33Krążek 22Krążek 11

Wybierz pręt początkowy, potem docelowy.

Wskazówki uwzględniają twój układ i nie przesuwają krążków. Dozwolone obejście nadal można dokończyć.

Jak rozwiązać Wieże Hanoi

Najpierw pomyśl o największym krążku. W przykładzie z czterema krążkami trzy małe go blokują. Rozwiąż mniejszy problem przed ruchem krążka 4.

  1. Odsuń mały stos

    Przenieś krążki 1, 2 i 3 z A na B, używając C pomocniczo. Krążek 4 zostaje na A. C jest wolny, a krążek 4 odsłonięty.

    ABCKrążek 44Krążek 33Krążek 22Krążek 11

  2. Przenieś największy krążek

    Przenieś krążek 4 z A na C. Ten jeden ruch ustawia go na miejscu końcowym.

    ABCKrążek 44Krążek 33Krążek 22Krążek 11

  3. Przenieś mały stos do celu

    Przenieś krążki 1, 2 i 3 z B na C, używając A pomocniczo. Mieszczą się na krążku 4 i zadanie jest rozwiązane.

    ABCKrążek 44Krążek 33Krążek 22Krążek 11

Każdy mniejszy stos stosuje ten sam plan: odsunąć krążki nad największym, przenieść go, a potem postawić na nim mały stos. Przy jednym krążku przenieś go bezpośrednio. To rekurencja; role początku, celu i pomocniczego pręta zmieniają się w każdym podproblemie.

Ucz się, przewidując następny cel

Osobne przykłady z czterema krążkami nie zmieniają twojej gry. Zatrzymaj pokaz, obejrzyj ruch, odpowiedz na pytanie lub odkryj wyjaśnienie.

1. Uwolnij największy krążek

Zobacz, jak trzy małe krążki robią miejsce dla krążka 4. Przewidź, gdzie mają być przed jego ruchem.

Osobny przykład z czterema krążkami

Cel: przenieść 3 krążków z A na B, używając C pomocniczo.

ABCKrążek 44Krążek 33Krążek 22Krążek 11

Najpierw zrób miejsce: przenieś trzy górne krążki z A na B.

Krok 0 z 8

2. Powtórz mniejszy problem

Krążek 4 jest już na C. Zostaje ten sam problem z trzema krążkami i nowymi rolami prętów.

Osobny przykład z czterema krążkami

Cel: przenieść 3 krążków z B na C, używając A pomocniczo.

ABCKrążek 44Krążek 33Krążek 22Krążek 11

Krążek 4 zostaje na C. Rozwiąż teraz trzy krążki z B na C.

Gdzie najpierw trafi krążek 1, gdy przenosisz trzy z B na C z pomocą A?

Krok 0 z 7

Rozwiązania krok po kroku

Przykłady zaczynają się ze wszystkimi krążkami na A i kończą na C. Otwieraj je od razu; twoja gra pozostaje bez zmian.

Minimalna liczba ruchów

T(n) = 2T(n − 1) + 1 = 2ⁿ − 1

Standardowe rozwiązanie przenosi mały stos dwa razy, a największy krążek raz: T(n) = 2T(n − 1) + 1. Jeden krążek wymaga jednego ruchu, więc minimum dla n krążków to 2ⁿ − 1.

3 krążki: 7 ruchów. 4 krążki: 15 ruchów. 5 krążków: 31 ruchów.

Krążki: 3 — ruchy: 7

Początek: wszystkie krążki na A. Cel: C. Krążek 1 jest najmniejszy.

  1. Przenieś krążek 1 z A na C.
  2. Przenieś krążek 2 z A na B.
  3. Przenieś krążek 1 z C na B.
  4. Przenieś krążek 3 z A na C.
  5. Przenieś krążek 1 z B na A.
  6. Przenieś krążek 2 z B na C.
  7. Przenieś krążek 1 z A na C.
Krążki: 4 — ruchy: 15

Początek: wszystkie krążki na A. Cel: C. Krążek 1 jest najmniejszy.

  1. Przenieś krążek 1 z A na B.
  2. Przenieś krążek 2 z A na C.
  3. Przenieś krążek 1 z B na C.
  4. Przenieś krążek 3 z A na B.
  5. Przenieś krążek 1 z C na A.
  6. Przenieś krążek 2 z C na B.
  7. Przenieś krążek 1 z A na B.
  8. Przenieś krążek 4 z A na C.
  9. Przenieś krążek 1 z B na C.
  10. Przenieś krążek 2 z B na A.
  11. Przenieś krążek 1 z C na A.
  12. Przenieś krążek 3 z B na C.
  13. Przenieś krążek 1 z A na B.
  14. Przenieś krążek 2 z A na C.
  15. Przenieś krążek 1 z B na C.
Krążki: 5 — ruchy: 31

Początek: wszystkie krążki na A. Cel: C. Krążek 1 jest najmniejszy.

  1. Przenieś krążek 1 z A na C.
  2. Przenieś krążek 2 z A na B.
  3. Przenieś krążek 1 z C na B.
  4. Przenieś krążek 3 z A na C.
  5. Przenieś krążek 1 z B na A.
  6. Przenieś krążek 2 z B na C.
  7. Przenieś krążek 1 z A na C.
  8. Przenieś krążek 4 z A na B.
  9. Przenieś krążek 1 z C na B.
  10. Przenieś krążek 2 z C na A.
  11. Przenieś krążek 1 z B na A.
  12. Przenieś krążek 3 z C na B.
  13. Przenieś krążek 1 z A na C.
  14. Przenieś krążek 2 z A na B.
  15. Przenieś krążek 1 z C na B.
  16. Przenieś krążek 5 z A na C.
  17. Przenieś krążek 1 z B na A.
  18. Przenieś krążek 2 z B na C.
  19. Przenieś krążek 1 z A na C.
  20. Przenieś krążek 3 z B na A.
  21. Przenieś krążek 1 z C na B.
  22. Przenieś krążek 2 z C na A.
  23. Przenieś krążek 1 z B na A.
  24. Przenieś krążek 4 z B na C.
  25. Przenieś krążek 1 z A na C.
  26. Przenieś krążek 2 z A na B.
  27. Przenieś krążek 1 z C na B.
  28. Przenieś krążek 3 z A na C.
  29. Przenieś krążek 1 z B na A.
  30. Przenieś krążek 2 z B na C.
  31. Przenieś krążek 1 z A na C.

A jeśli mój układ różni się od przykładu?

Każdy układ zgodny z rozmiarami może dojść do C. Powtórzona pozycja to pętla, nie ślepa uliczka. Wzór dotyczy standardowego początku, nie pozostałych ruchów z dowolnego układu. Poproś o wskazówkę dla swojej pozycji.

Łamigłówki →