Na ile sposobów można pomalować płot

kalwi · Post autor: **kalwi** » 15 cze 2016, o 04:27

Mamy sobie płot złożony z \(\displaystyle{ n}\) desek. Mamy 2 kolory farby. Możemy pomalować płot tak, że co najwyżej 2 deski obok siebie mogą być w tym samym kolorze. Na ile sposobów można pomalować cały płot?

Majeskas · Post autor: **Majeskas** » 15 cze 2016, o 11:40

Wskazówka: Oznaczyć przez \(\displaystyle{ a_n}\) liczbę sposobów pomalowania płotu długości \(\displaystyle{ n}\) i napisać rekurencję.

kalwi · Post autor: **kalwi** » 16 cze 2016, o 00:36

No to wyszedł mi ciąg ala Fibbonacci,

\(\displaystyle{ F(n) = \begin{cases} 2 \ \text{dla} \ n = 1 \\ 4 \ \text{dla} \ n = 2 \\ F_{n-1}+F_{n-2} \ \text{dla} \ n > 2 \end{cases}}\)

Tylko pytanie brzmi, czym można tu coś pokombinować nierekurencyjnie?

arek1357 · Post autor: **arek1357** » 16 cze 2016, o 11:41