Witam,
Mam duży problem z zadaniem o nastepującej treści: "Na ile sposobów można pokonać drogę złożoną z
n schodków, gdy za każdym razem przeskakujemy jeden stopień lub
dwa?". Bardzo prosze o naprowadzenie mnie od czego powinienem zacząć rozwiązywać ten problem, i jeżeli to mozliwe o rozwiązanie żebym mogł potem sie sprawdzić.
Z góry dziękuje
Na ile sposobów można pokonać n stopni
Na ile sposobów można pokonać n stopni
Domyślam się że chodzi tu własnie o ułożenie zależności rekurencyjnej, ale z tym mam problem.
-
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
Na ile sposobów można pokonać n stopni
Przypuśćmy, że wiemy na ile sposobów można dostać się na \(\displaystyle{ k < n}\) stopni. Oznaczmy tę liczbę przez \(\displaystyle{ a_k}\). Na ile sposobów (korzystając z tych danych) możemy wejść na stopień \(\displaystyle{ n}\)-ty? Podpowiedź - możemy na niego wejść ze stopnia o numerze \(\displaystyle{ n-1}\) lub \(\displaystyle{ n-2}\).
Na ile sposobów można pokonać n stopni
Skoro wiemy ze na stopien \(\displaystyle{ a_1 = 1}\) i \(\displaystyle{ a_2 = 2}\) mozemy napisac wzór \(\displaystyle{ a_n = a_{n-1} + a_{n-2}}\) gdzie \(\displaystyle{ a_n}\) jest iloścą sposobów wejscia na \(\displaystyle{ n-ty}\) stopień?