Mam problem ze znajdowaniem funkcji rekurencyjnych dla problemów kombinatorycznych. Ostatnio "zaciąłem się" na czymś takim:
Niech p(n) oznacza ilosc ciagów binarnych dł. n, które nie zawierają 3 jedynek na sąsiednich miejscach. Znaleźć wzór rekurencyjny p(n).
Jeżeli byłoby, że nie moze być 2 jedynek, to problem byłby wręcz banalny (p(n) = p(n-1) + p(n-2) o ile się nie mylę)...
Kolejnym podobnym zadaniem jest takie, w którym w warunku zamiast 3 jedynek mamy "ilosc jedynek w ciągu jest podzielna przez 4" - z tym też mam duże kłopoty.
Byłbym wdzięczny za wszelką pomoc.
ciągi binarne a rekurencja
-
półpasiec
- Gość Specjalny
- Posty: 534
- Rejestracja: 8 lip 2004, o 17:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 17 razy
ciągi binarne a rekurencja
to z trzema kolejnymi jedynkami zrobilbym tak
niech \(\displaystyle{ p(n)}\) oznacza ilosc takich ciagow dlugosci \(\displaystyle{ n}\), niech tez
\(\displaystyle{ p_0(n)}\) to ilosc takich ciagow ale przy tym na pierwszych dwu pozycjach nie wystepuja jedynki, \(\displaystyle{ p_1(n)}\) na pierwszych dwu wystepuje jedna jedynka, \(\displaystyle{ p_2(n)}\) na pierwszych dwu wystepuja dwie jedynki
no to \(\displaystyle{ p_0(n)+p_1(n)+p_2(n)=p(n)}\)
teraz widac ze \(\displaystyle{ p(n+1)=2p_0(n)+2p_1(n)+p_2(n)}\)
bo jak na pierwszych dwu nie bylo dwu jedynek to mozemy na pierwsza pozycje dac dwie liczby, a jak pierwsze dwie to jedynki to mozemy tylko dac 0
zatem \(\displaystyle{ p(n+1)=2p(n)-p_2(n)}\)
wystarczy obliczyc \(\displaystyle{ p_2(n)}\), jego przod musi wygladac tak \(\displaystyle{ 110...}\)
wiec piersze trzy pozycje sa obstawione a na wczesniejsze \(\displaystyle{ n-3}\) pozycji mozemy ustawic je dowolnie, byle poprawnie wiec na \(\displaystyle{ p(n-3)}\) sposobow
zatem \(\displaystyle{ p_2(n)=p(n-3)}\)
zatem \(\displaystyle{ p(n+1)=2p(n)-p(n-3)}\)
mozna dalej sie pobawic z \(\displaystyle{ p_i}\) i dostac cos podobnego do \(\displaystyle{ p_2(n)=p(n-3)}\) i moze uzyska sie zwiazek zalezny od trzech kolejnych a nie taki z przerwa 3
niech \(\displaystyle{ p(n)}\) oznacza ilosc takich ciagow dlugosci \(\displaystyle{ n}\), niech tez
\(\displaystyle{ p_0(n)}\) to ilosc takich ciagow ale przy tym na pierwszych dwu pozycjach nie wystepuja jedynki, \(\displaystyle{ p_1(n)}\) na pierwszych dwu wystepuje jedna jedynka, \(\displaystyle{ p_2(n)}\) na pierwszych dwu wystepuja dwie jedynki
no to \(\displaystyle{ p_0(n)+p_1(n)+p_2(n)=p(n)}\)
teraz widac ze \(\displaystyle{ p(n+1)=2p_0(n)+2p_1(n)+p_2(n)}\)
bo jak na pierwszych dwu nie bylo dwu jedynek to mozemy na pierwsza pozycje dac dwie liczby, a jak pierwsze dwie to jedynki to mozemy tylko dac 0
zatem \(\displaystyle{ p(n+1)=2p(n)-p_2(n)}\)
wystarczy obliczyc \(\displaystyle{ p_2(n)}\), jego przod musi wygladac tak \(\displaystyle{ 110...}\)
wiec piersze trzy pozycje sa obstawione a na wczesniejsze \(\displaystyle{ n-3}\) pozycji mozemy ustawic je dowolnie, byle poprawnie wiec na \(\displaystyle{ p(n-3)}\) sposobow
zatem \(\displaystyle{ p_2(n)=p(n-3)}\)
zatem \(\displaystyle{ p(n+1)=2p(n)-p(n-3)}\)
mozna dalej sie pobawic z \(\displaystyle{ p_i}\) i dostac cos podobnego do \(\displaystyle{ p_2(n)=p(n-3)}\) i moze uzyska sie zwiazek zalezny od trzech kolejnych a nie taki z przerwa 3
ciągi binarne a rekurencja
Tak na szybko policzyłem ręcznie ilość dozwolonych kombinacji dla kilku pierwszych długości i wyszło mi coś takiego:
p(1) = 2
p(2) = 4
p(3) = 7
p(4) = 14
p(5) = 29
p(6) = 60
I nie zgadzają się te wartości z przedstawioną rekurencją. Albo ja coś źle licze, albo jest jakiś błąd.
p(1) = 2
p(2) = 4
p(3) = 7
p(4) = 14
p(5) = 29
p(6) = 60
I nie zgadzają się te wartości z przedstawioną rekurencją. Albo ja coś źle licze, albo jest jakiś błąd.
ciągi binarne a rekurencja
Fakt, mój błąd.
Nie wziąłem pod uwagę wielu ciągów, które spełniają warunki zadania. Jak wszystko dokładnie podliczyłem, to się zgadza.
Nie wziąłem pod uwagę wielu ciągów, które spełniają warunki zadania. Jak wszystko dokładnie podliczyłem, to się zgadza.