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.
Zależność rekurencyjna
- Jestemfajny
- 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
-
- 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
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.
\(\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.
- Jestemfajny
- 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
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??