Rekurencja - wyprowadzanie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Spheros
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 21 sty 2007, o 13:11
Płeć: Mężczyzna
Lokalizacja: Zawiercie
Podziękował: 2 razy
Pomógł: 1 raz

Rekurencja - wyprowadzanie

Post autor: Spheros » 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?

frej

Rekurencja - wyprowadzanie

Post autor: frej » 17 maja 2009, o 19:48

Jak pierwszy jest \(\displaystyle{ a}\), to drugi, może być na dwie możliwości , a trzeci to \(\displaystyle{ g_{n-2}}\)
Jak pierwszy nie jest \(\displaystyle{ a}\), to mamy 2 możliwości, a reszta, to \(\displaystyle{ g_{n-1}}\)

Spheros
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 21 sty 2007, o 13:11
Płeć: Mężczyzna
Lokalizacja: Zawiercie
Podziękował: 2 razy
Pomógł: 1 raz

Rekurencja - wyprowadzanie

Post autor: Spheros » 17 maja 2009, o 21:12

Nie rozumiem Twojej wypowiedzi niestety mógłbyś rozwinąć?

Awatar użytkownika
miss.waikiki
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 28 sty 2008, o 14:19
Płeć: Kobieta
Lokalizacja: Waikiki
Podziękował: 2 razy
Pomógł: 4 razy

Rekurencja - wyprowadzanie

Post autor: miss.waikiki » 15 cze 2009, o 00:49

Jesteś z wms?

ODPOWIEDZ