Należy podać ilość sposobów na jaką można ulożyc płytki o długości 2x1 na podłodze o wymiarach 3xn.
Problem jest przy liczbie n-nieparzystej, gdyż można płytki układać tak aby wystawały, lecz to "wystawanie" płytki nie jest rozpatrywane na pion czy poziom(liczy sie jako 1 kombinacja).
dla:
n=1 liczba kombinacji 2
n=2 liczba kombinacji 3
n=3 liczba kombinacji 16
n=4 liczba kombinacji 9
Widzę tu jakąś zasadę, ale nie potrafie ułożyc jednego wzoru.
PS Muszę napisać funkcje w c++, więc mozna ułożyc 2 wzory z podziałem na liczby parzyste i nieparzyste
Ilosc sposobow,podloga- nx3 plytki- 2x1
-
dejwid13_93
- Użytkownik
- Posty: 2
- Rejestracja: 11 mar 2011, o 17:31
- Płeć: Mężczyzna
- Lokalizacja: kraków
-
norwimaj
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Ilosc sposobow,podloga- nx3 plytki- 2x1
Rozpatrzmy dwa ciągi. \(\displaystyle{ a_n}\) to liczba ustawień płytek, pokrywających podłogę \(\displaystyle{ n\times3}\). \(\displaystyle{ b_n}\) to liczba pokryć podłogi \(\displaystyle{ n\times3}\) bez jednego, konkretnego rogu.
Rozpatrując przypadki ustawień ostatnich płytek, można znaleźć wzory rekurencyjne:
\(\displaystyle{ a_n=a_{n-2}+2b_{n-1}\qquad b_n=a_{n-1}+b_{n-2}}\). Stąd mamy równość:
\(\displaystyle{ \left(\begin{array}{c}a_n\\a_{n-1}\\b_n\\b_{n-1}\end{array}\right) = A\cdot
\left(\begin{array}{c}a_{n-1}\\a_{n-2}\\b_{n-1}\\b_{n-2}\end{array}\right)}\),
gdzie
\(\displaystyle{ A=\left(\begin{array}{cccc}0&1&2&0\\1&0&0&0\\1&0&0&1\\0&0&1&0\end{array}\right)}\).
Ta równość wystarcza do napisania programu działającego w czasie \(\displaystyle{ \Theta(\log{n})}\). Wystarczy policzyć odpowiednią potęgę macierzy \(\displaystyle{ A}\) i przyłożyć ją do początkowych wyrazów ciągu.
Można też za pomocą postaci Jordana macierzy \(\displaystyle{ A}\) wyliczyć jawne wzory na te ciągi, ale w ten sposób prawdopodobnie nie napiszesz szybszego programu, a poza tym byś musiał działać na liczbach zmiennoprzecinkowych, albo nawet zespolonych. W rozwiązaniu z potęgowaniem macierzy wystarczą liczby całkowite.
-- 11 mar 2011, o 18:56 --
Dodam jeszcze, że dla \(\displaystyle{ n}\) parzystych \(\displaystyle{ b_n=0}\) a dla \(\displaystyle{ n}\) nieparzystych \(\displaystyle{ a_n=0}\). To, czego szukasz (jeśli dobrze rozumiem), to \(\displaystyle{ a_n}\) dla \(\displaystyle{ n}\) parzystych i \(\displaystyle{ 4b_n}\) dla \(\displaystyle{ n}\) nieparzystych, większych niż \(\displaystyle{ 1}\). Dla \(\displaystyle{ n=4}\) wychodzi \(\displaystyle{ 11}\) a nie \(\displaystyle{ 9}\).
Jeśli za bardzo przestraszyłem, to pocieszę, że wartości własne wychodzą chyba rzeczywiste, i to nawet łatwo dające się wyliczyć.
Rozpatrując przypadki ustawień ostatnich płytek, można znaleźć wzory rekurencyjne:
\(\displaystyle{ a_n=a_{n-2}+2b_{n-1}\qquad b_n=a_{n-1}+b_{n-2}}\). Stąd mamy równość:
\(\displaystyle{ \left(\begin{array}{c}a_n\\a_{n-1}\\b_n\\b_{n-1}\end{array}\right) = A\cdot
\left(\begin{array}{c}a_{n-1}\\a_{n-2}\\b_{n-1}\\b_{n-2}\end{array}\right)}\),
gdzie
\(\displaystyle{ A=\left(\begin{array}{cccc}0&1&2&0\\1&0&0&0\\1&0&0&1\\0&0&1&0\end{array}\right)}\).
Ta równość wystarcza do napisania programu działającego w czasie \(\displaystyle{ \Theta(\log{n})}\). Wystarczy policzyć odpowiednią potęgę macierzy \(\displaystyle{ A}\) i przyłożyć ją do początkowych wyrazów ciągu.
Można też za pomocą postaci Jordana macierzy \(\displaystyle{ A}\) wyliczyć jawne wzory na te ciągi, ale w ten sposób prawdopodobnie nie napiszesz szybszego programu, a poza tym byś musiał działać na liczbach zmiennoprzecinkowych, albo nawet zespolonych. W rozwiązaniu z potęgowaniem macierzy wystarczą liczby całkowite.
-- 11 mar 2011, o 18:56 --
Dodam jeszcze, że dla \(\displaystyle{ n}\) parzystych \(\displaystyle{ b_n=0}\) a dla \(\displaystyle{ n}\) nieparzystych \(\displaystyle{ a_n=0}\). To, czego szukasz (jeśli dobrze rozumiem), to \(\displaystyle{ a_n}\) dla \(\displaystyle{ n}\) parzystych i \(\displaystyle{ 4b_n}\) dla \(\displaystyle{ n}\) nieparzystych, większych niż \(\displaystyle{ 1}\). Dla \(\displaystyle{ n=4}\) wychodzi \(\displaystyle{ 11}\) a nie \(\displaystyle{ 9}\).
Jeśli za bardzo przestraszyłem, to pocieszę, że wartości własne wychodzą chyba rzeczywiste, i to nawet łatwo dające się wyliczyć.