szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
PostNapisane: 16 wrz 2005, o 09:46 
Użytkownik
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. :-)
Góra
Mężczyzna
PostNapisane: 16 wrz 2005, o 16:23 
Gość Specjalny

Posty: 534
Lokalizacja: Warszawa
to z trzema kolejnymi jedynkami zrobilbym tak
niech p(n) oznacza ilosc takich ciagow dlugosci n, niech tez
p_0(n) to ilosc takich ciagow ale przy tym na pierwszych dwu pozycjach nie wystepuja jedynki, p_1(n) na pierwszych dwu wystepuje jedna jedynka, p_2(n) na pierwszych dwu wystepuja dwie jedynki
no to p_0(n)+p_1(n)+p_2(n)=p(n)
teraz widac ze 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 p(n+1)=2p(n)-p_2(n)
wystarczy obliczyc p_2(n), jego przod musi wygladac tak 110...
wiec piersze trzy pozycje sa obstawione a na wczesniejsze n-3 pozycji mozemy ustawic je dowolnie, byle poprawnie wiec na p(n-3) sposobow
zatem p_2(n)=p(n-3)
zatem p(n+1)=2p(n)-p(n-3)

mozna dalej sie pobawic z p_i i dostac cos podobnego do p_2(n)=p(n-3) i moze uzyska sie zwiazek zalezny od trzech kolejnych a nie taki z przerwa 3
Góra
Mężczyzna
PostNapisane: 16 wrz 2005, o 17:33 
Użytkownik

Posty: 3
Lokalizacja: Toruń
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.
Góra
Mężczyzna
PostNapisane: 16 wrz 2005, o 22:24 
Gość Specjalny

Posty: 534
Lokalizacja: Warszawa
zle liczysz
Góra
Mężczyzna
PostNapisane: 16 wrz 2005, o 23:26 
Użytkownik

Posty: 3
Lokalizacja: Toruń
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. :-)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ciągi pozycyjne  Dasio11  0
 Prosta rekurencja, co z nią nie tak?  Mabakay  6
 Rekurencja liniowa - zadanie 2  ktoslos  2
 rekurencja - podział prostokąta  nova  1
 Rekurencja w zadaniach  nowik1991  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl