Na ile sposobów można pokonać n stopni

rowuald · Post autor: **rowuald** » 23 cze 2013, o 03:06

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

bartek118 · Post autor: **bartek118** » 23 cze 2013, o 06:38

Ułóż zależność rekurencyjną.

rowuald · Post autor: **rowuald** » 23 cze 2013, o 10:08

Domyślam się że chodzi tu własnie o ułożenie zależności rekurencyjnej, ale z tym mam problem.

bartek118 · Post autor: **bartek118** » 23 cze 2013, o 15:25

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}\).

rowuald · Post autor: **rowuald** » 23 cze 2013, o 18:13

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ń?

bartek118 · Post autor: **bartek118** » 23 cze 2013, o 18:58

Zgadza się.