Mam zadanie, które nie raz już się przewijało. Mam jedno pytanie:
Zliczyć na ile sposobów można pokryć prostokąt 2 × n kostkami domina (czyli prostokącikami 1 × 2).
Umiem dojść do prawidłowej rekurencji, ale nie mogę zrozumieć dlaczego warunek dla n = 0 jest równy 1. W internecie jest napisane, że to oczywiste. prostokąt o wymiarach 2 x 0 nie może być pokryty kostkami. Wynikałoby z tego, że ten brak możliwości liczymy jako możliwość. Potem kiedy już "możemy" ułożyć kostki domina ta "niemożność" znika?
Pozdrawiam,
Fray
Puste pokrycie prostokata
-
kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
Puste pokrycie prostokata
Jeden sposób jest dla \(\displaystyle{ n=1}\). https://www.matematyka.pl/299830.htm?hil ... t%20domino
-
Fray
- Użytkownik
- Posty: 52
- Rejestracja: 18 sty 2014, o 18:42
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 8 razy
Puste pokrycie prostokata
Podobno dla \(\displaystyle{ n = 0}\) podobno też jest jeden sposób. Porównując wynik do przesuniętego wzoru Bineta mam dobre rozwiązanie, ale nie wiem dlaczego należy przyjąć takie warunki.
Cytat:
"Rozpoznajemy w tym łatwo ciąg Fibonacci'ego \(\displaystyle{ d_n = f_{n+1}}\) (bo oczywiście pusty prostokąt \(\displaystyle{ 2 \times 0}\) można pokryć na dokładnie jeden sposób, \(\displaystyle{ d_0=1}\)). "
Cytat:
"Rozpoznajemy w tym łatwo ciąg Fibonacci'ego \(\displaystyle{ d_n = f_{n+1}}\) (bo oczywiście pusty prostokąt \(\displaystyle{ 2 \times 0}\) można pokryć na dokładnie jeden sposób, \(\displaystyle{ d_0=1}\)). "