ciągi rekurencyjne
sp33dy: Ile jest słów długości n złożonych z liter a; b; c; w których nie ma dwóch kolejnych a? Znajdź
zależność rekurencyjną
1 gru 12:25
Pytający:
Oznaczmy:
"takich słów" = "słów długości n złożonych z liter a; b; c; w których nie ma dwóch kolejnych a"
an // takich słów, gdzie ostatnia litera to 'a'
bn // takich słów, gdzie ostatnia litera jest różna od 'a' (czyli 'b' lub 'c')
cn // takich słów
Wtedy:
a1=1 // "a"
b1=2 // "b", "c"
an=bn−1, n>1 // 'a' można dołączyć jedynie jeśli ostatnia litera jest różna od 'a'
bn=2(an−1+bn−1), n>1 // 'b' lub 'c' można zawsze dołączyć
cn=an+bn, n≥1
c1=a1+b1=1+2=3
cn=an+bn=bn−1+2(an−1+bn−1)=bn−1+2cn−1, n>1
c2=b1+2c1=2+2*3=8
cn=bn−1+2cn−1=2(an−2+bn−2)+2cn−1=2cn−2+2cn−1, n>2
c1=3
c2=8
cn=2(cn−1+cn−2), n>2
1 gru 16:29