Na ile sposobów można pomalować płot
-
- Użytkownik
- Posty: 1931
- Rejestracja: 29 maja 2009, o 11:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 145 razy
- Pomógł: 320 razy
Na ile sposobów można pomalować płot
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?
-
- Użytkownik
- Posty: 1456
- Rejestracja: 14 gru 2007, o 14:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 49 razy
- Pomógł: 198 razy
Na ile sposobów można pomalować płot
Wskazówka: Oznaczyć przez \(\displaystyle{ a_n}\) liczbę sposobów pomalowania płotu długości \(\displaystyle{ n}\) i napisać rekurencję.
-
- Użytkownik
- Posty: 1931
- Rejestracja: 29 maja 2009, o 11:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 145 razy
- Pomógł: 320 razy
Na ile sposobów można pomalować płot
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?
\(\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?