Zależność rekurencyjna

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
Jestemfajny
Użytkownik
Użytkownik
Posty: 187
Rejestracja: 22 lis 2006, o 21:08
Płeć: Mężczyzna
Lokalizacja: AGH
Podziękował: 10 razy
Pomógł: 36 razy

Zależność rekurencyjna

Post autor: Jestemfajny »

Mam problem z takim zadaniem:
Ile jest ciągów binarnych długości n w których żadne 3 zera nie występują obok siebie??-znajdź zależność rekurencyjną.
Ogolnie to gdyby ktoś przybliżył sposób rozwiązywania takich zadań to było by super;)
Pozdrawiam.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Zależność rekurencyjna

Post autor: »

Rekurencja:
\(\displaystyle{ \begin{cases}
a_1=2 \\
a_2 = 4 \\
a_3 = 7 \\
a_4 = 13 \\
a_n = a_{n-1} + (a_{n-1} - a_{n-4}) \ dla \ n q 5
\end{cases}}\)


Ciągi n-elementowe o żądanej własności dzielimy na te, które się kończą jedynkę i na te, które zerem i patrzymy jak musi wyglądać pierwszych (n-1) wyrazów ciągu. W pierwszym wypadku dowolnie, w drugim - prawie dowolnie, nie może się tylko kończyć na 100. Stąd wzór rekurencyjny.

Q.
Awatar użytkownika
Jestemfajny
Użytkownik
Użytkownik
Posty: 187
Rejestracja: 22 lis 2006, o 21:08
Płeć: Mężczyzna
Lokalizacja: AGH
Podziękował: 10 razy
Pomógł: 36 razy

Zależność rekurencyjna

Post autor: Jestemfajny »

No tak..ciekawe...szczerze....i tak nie rozumiem.A napisałbys wzór(ogólny) na ilość ciągów binarnych w których 3 istnieja 3 zera pokolei??
ODPOWIEDZ