Ile jest ciągów długości n złożonych z 0,1, które nie zawierają trzech jedynek na sąsiednich miejscach. Znaleźć zależność rekurencyjną.
Ile jest ciągów długości n złożonych z 0,1, które zawierają parzystą liczbę 1 i każde dwie jedynki rozdzielone są przynajmniej jednym 0. Znaleźć zależność rekurencyjną.
Proszę o pomoc
Rekurencja - ilość ciągów binarnych
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Guru
- Posty: 17549
- Rejestracja: 09 lis 2010, 07:38
- Lokalizacja: Warszawa
- Podziękowania: 41 razy
- Otrzymane podziękowania: 7435 razy
- Płeć:
Re: Rekurencja - ilość ciągów binarnych
wszystkich ciągów długości n złożonych z 0,1 jest \(2^n\),mmatix pisze:Ile jest ciągów długości n złożonych z 0,1, które nie zawierają trzech jedynek na sąsiednich miejscach. Znaleźć zależność rekurencyjną.
tych, które zawierają trzy jedynki jest \(n-2\)
No to tych, które nie zawierają jest \(2^n-n+2\)
Chcesz rekurencyjnie wiec \(a_3=7\\a_{n+1}=a_n+2^n-1\)