Rekurencja - wyprowadzanie
: 17 maja 2009, o 18:56
Witam. Mam dwa zadania. Jedno teoretycznie rozwiązałem, ale prosiłbym o weryfikację metody.
1)Ile jest słów długośc n złożonych z liter a, b, c, w których nie ma dwóch kolejnych liter a? Znajdz zaleznosc rekurencyjna oraz wzór.
Tego nie wiem. Znam rozwiązanie teoretycznego przypadku, gdy żadna litera nie może się powtarzać po sobie
2) Ile jest różnych sposobów wejscia po schodach zbudowanych z n stopni, jezeli w kazdym kroku mozna pokonac jeden lub dwa stopnie? Znajdz zaleznosc rekurencyjna oraz wzór.
tutaj tak:
mamy \(\displaystyle{ n}\) schodków.
Możemy skoczyć o dwa schodki:
wtedy zostaje nam \(\displaystyle{ n-2}\) schodkow do przeskoczenia.
Ewentualnie możemy skoczyć o 1 schodek:
zostaje nam \(\displaystyle{ n-1}\) schodkow.
Zatem wzór rekurencyjny wyraża się \(\displaystyle{ p_{n}=p_{n-1}+p_{n-2}}\). A wzór ogólny wzorem Bineta. Dobrze?
1)Ile jest słów długośc n złożonych z liter a, b, c, w których nie ma dwóch kolejnych liter a? Znajdz zaleznosc rekurencyjna oraz wzór.
Tego nie wiem. Znam rozwiązanie teoretycznego przypadku, gdy żadna litera nie może się powtarzać po sobie
2) Ile jest różnych sposobów wejscia po schodach zbudowanych z n stopni, jezeli w kazdym kroku mozna pokonac jeden lub dwa stopnie? Znajdz zaleznosc rekurencyjna oraz wzór.
tutaj tak:
mamy \(\displaystyle{ n}\) schodków.
Możemy skoczyć o dwa schodki:
wtedy zostaje nam \(\displaystyle{ n-2}\) schodkow do przeskoczenia.
Ewentualnie możemy skoczyć o 1 schodek:
zostaje nam \(\displaystyle{ n-1}\) schodkow.
Zatem wzór rekurencyjny wyraża się \(\displaystyle{ p_{n}=p_{n-1}+p_{n-2}}\). A wzór ogólny wzorem Bineta. Dobrze?