ułożyć wzór rekurencyjny
-
- Użytkownik
- Posty: 63
- Rejestracja: 16 sty 2009, o 08:48
- Podziękował: 12 razy
ułożyć wzór rekurencyjny
Na ile sposobów można ułożyć chodnik długości n jednostek mając do dyspozycji niebieskie płytki długości jednej jednostki oraz zielone i czerwone płytki długości dwóch jednostek.
- Szemek
- Użytkownik
- Posty: 4819
- Rejestracja: 10 paź 2006, o 23:03
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 43 razy
- Pomógł: 1407 razy
ułożyć wzór rekurencyjny
\(\displaystyle{ h_n}\) - liczba możliwych ułożeń chodnika o długości \(\displaystyle{ n}\)
\(\displaystyle{ h_n = h_{n-1} + 2h_{n-2}}\)
Do chodnika o długości \(\displaystyle{ n-1}\) możemy dołożyć tylko jedną płytkę o długości \(\displaystyle{ 1}\), a do chodnika o długości \(\displaystyle{ n-2}\) możemy dołożyć jedną z dwóch płytek o długości \(\displaystyle{ 2}\).
Nie rozpatrujemy przypadku dołożenia dwóch płytek o długości \(\displaystyle{ 1}\), ponieważ dokładając jedną taką płytkę otrzymujemy przypadek chodnika o długości \(\displaystyle{ n-1}\).
\(\displaystyle{ h_n = h_{n-1} + 2h_{n-2}}\)
Do chodnika o długości \(\displaystyle{ n-1}\) możemy dołożyć tylko jedną płytkę o długości \(\displaystyle{ 1}\), a do chodnika o długości \(\displaystyle{ n-2}\) możemy dołożyć jedną z dwóch płytek o długości \(\displaystyle{ 2}\).
Nie rozpatrujemy przypadku dołożenia dwóch płytek o długości \(\displaystyle{ 1}\), ponieważ dokładając jedną taką płytkę otrzymujemy przypadek chodnika o długości \(\displaystyle{ n-1}\).
-
- Użytkownik
- Posty: 63
- Rejestracja: 16 sty 2009, o 08:48
- Podziękował: 12 razy
ułożyć wzór rekurencyjny
A gdy będziemy mieli niebieskie płytki długości dwóch jednostek oraz zielone i czerwone długości jednej jednostki to odpowiedź będzie podobna?