szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 11 mar 2011, o 18:39 
Użytkownik

Posty: 2
Lokalizacja: kraków
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
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 11 mar 2011, o 19:15 
Użytkownik

Posty: 5101
Lokalizacja: 52°16'37''N 20°52'45''E
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ć.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość liczb nat nie dzielących się przez  Honzik18  7
 Ciąg liczbowy, ilość liczb z tego zbioru.  AdiPL  1
 Na ile sposobów można rozdzielić...  james007pl  3
 liczba sposobów rozłożenia liczby na trzy czynniki  WolfusA  3
 funkcja tworząca - na ile sposobow mozna kupic  supeextra5  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl