Prezentacja multimedialna
Zagadka Wież Hanoi polega na przeniesieniu krążków o różnych rozmiarach z jednego słupka na drugi. Warunkiem poprawnego rozwiązania zadania jest przenoszenie każdego krążka pojedynczo, a także brak możliwości położenia większego na mniejszym. Do dyspozycji mamy pomocniczy słupek, na który również możemy odkładać krążki podczas przenoszenia. Algorytm rozwiązujący tę zagadkę został zaprezentowany w postaci pseudokodu.
Pseudokod:
Zadanie 1.3
Przeanalizuj działanie przedstawionego algorytmu. Na jego podstawie uzupełnij tabelę.
Niech H(n) oznacza liczbę ruchów wykonanych dla n krążków. Zauważ, że rozwiązanie problemu dla n > 1 krążków wymaga jednego ruchu oraz dwukrotnego rozwiązania problemu dla n - 1 krążków. W oparciu o tę obserwację uzupełnij poniższą tabelę.
n | H(n) |
|---|---|
1 | 1 |
2 | 3 |
3 | |
4 | |
5 | |
7 | |
10 |
Podaj ogólny wzór określający liczbę ruchów dla n krążków
Zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i znajduje się w Maturalnym zbiorze zadań z informatyki, dostępnym na stronie internetowej CKE.
Zapoznaj się z prezentacją wyjaśniającą, jak obliczyć czas potrzebny mnichom do rozwiązania zagadki. Zakładamy, że przeniesienie jednego krążka trwa sekundę.