Question

mamy 14 schodów. Na ile sposobów mozemy na nie wejsc jesli mozemy robic krok co jeden i co dwa schody? potrzebuje to koniecznie jesli bedzie poprawnie rozwiazane daje naj

Answer 1

Ilosc sposobow wejscia w ten sposob na n schodow tworza kolejne wyrazy ciagu Fibonacciego.

Mozemy wejsc na I schodek i dalej na P(n-1) sposobow lub na II schodek i dalej na P(n-2) sposobow.

P(n)=P(n-1)+P(n-2)

F_n-1+F_n-2=F_n+1 dla n>1

P(n)=F_(n+1)

 

Dla n=14, jest to 15-ty wyraz ciagu Fibonacciego, ktory mozna obliczyc w sposob jawny ze wzoru Bineta.

Wartosci wyrazow w zalaczniku.

F_15= 610

Odp. Na 610 sposobow.