Ilosc sposobow,podloga- nx3 plytki- 2x1

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
dejwid13_93
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 11 mar 2011, o 17:31
Płeć: Mężczyzna
Lokalizacja: kraków

Ilosc sposobow,podloga- nx3 plytki- 2x1

Post autor: dejwid13_93 » 11 mar 2011, o 17:39

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

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E

Ilosc sposobow,podloga- nx3 plytki- 2x1

Post autor: norwimaj » 11 mar 2011, o 18:15

Rozpatrzmy dwa ciągi. \(a_n\) to liczba ustawień płytek, pokrywających podłogę \(n\times3\). \(b_n\) to liczba pokryć podłogi \(n\times3\) bez jednego, konkretnego rogu. Rozpatrując przypadki ustawień ostatnich płytek, można znaleźć wzory rekurencyjne: \(a_n=a_{n-2}+2b_{n-1}\qquad b_n=a_{n-1}+b_{n-2}\). Stąd mamy równość: \(\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 \(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 \(\Theta(\log{n})\). Wystarczy policzyć odpowiednią potęgę macierzy \(A\) i przyłożyć ją do początkowych wyrazów ciągu. Można też za pomocą postaci Jordana macierzy \(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 \(n\) parzystych \(b_n=0\) a dla \(n\) nieparzystych \(a_n=0\). To, czego szukasz (jeśli dobrze rozumiem), to \(a_n\) dla \(n\) parzystych i \(4b_n\) dla \(n\) nieparzystych, większych niż \(1\). Dla \(n=4\) wychodzi \(11\) a nie \(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ć.

ODPOWIEDZ