Zbiór zadań, (zadania różne)
Zadanie 174
Na ile sposobów można wejść na wieżę, jeśli wiadomo, że na wieżę prowadzą schody z 12 stopniami i w każdym kroku można pokonać jeden lub dwa stopnie?
Rozwiązanie
Niech n oznacza liczbę stopni, an - liczbę możliwych wejść na wieżę.
Dla:
n = 1, a1 = 1
n = 2, a2 = 2; {1,1}, {2};
n = 3, a3 = 3; {1,1,1}, {1,2}, {2,1};
n = 4, a4 = 5; {1,1,1,1}, {1,1,2}, {1,2,1}, {2,1,1}, {2,2};
n = 5, a5 = 8; {1,1,1,1,1}, {1,1,1,2}, {1,1,2,1}, {1,2,1,1}, {2,1,1,1}, {1,2,2}, {2,1,2}, {2,2,1},;
Stąd wniosek, że: an = an-1 + an-2 dla n > 2.
Jest to rekurencyjny wzór znajdujący rozwiązanie dla danego zadania. Wyrazy tego ciągu są jednocześnie wyrazami ciągu Fibonacciego.
Dla n = 12 mamy a12 = 233.
Na wieżę można wejść na 233 różne sposoby.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>