Baza wiedzy/Zagadki/Wieże Hanoi
Matematykałatwy

Wieże Hanoi

Wieże Hanoi
Wieże Hanoi Trzy słupki i wieża krążków; minimalna liczba ruchów dla n krążków to 2 do potęgi n minus 1. Wieże Hanoi — 2ⁿ − 1 ruchów n krążków → 2ⁿ − 1 3 krążki → 7 5 krążków → 31 10 krążków → 1 023 64 krążki → ~1,8·10¹⁹ 64 krążki po ruchu na sekundę: ~585 miliardów lat — dłużej niż istnieje Wszechświat. Każdy dodatkowy krążek podwaja liczbę ruchów — to istota rekurencji.

Pytanie

Przełóż wieżę krążków na inny słupek (większy nigdy na mniejszym, po jednym na raz). Dla 64 krążków — ile ruchów?

Najpierw spróbuj zgadnąć — dopiero potem odsłoń podpowiedź.

PodpowiedźPokaż

Każdy dodatkowy krążek podwaja liczbę ruchów.

Pokaż rozwiązanie

2⁶⁴ − 1 = ponad 18 trylionów ruchów.

Moment „aha”

Minimalna liczba ruchów dla n krążków to 2ⁿ − 1. Wedle legendy mnisi układający 64 krążki skończą u kresu świata — nawet po ruchu na sekundę zajęłoby to ~585 miliardów lat. Wzorcowy przykład rekurencji.

Powiązania

Matematyka przez wiekiścieżkaMaszyny licząceścieżka

Ciekawa zagadka? Udostępnij.

Za darmo w NexTutor — rzuć komuś wyzwanie.

Uczysz? Umieść tę zagadkę na swojej stronie.

Darmowy widget — wklej na stronę szkoły, bloga lub notatki. Linkuje do pełnej wersji.

Uczysz w klasie albo korepetujesz? Prowadź uczniów w NexTutor →