2013-05-05 9 views
6

Próbowałem rozwiązać this programming problem, ale ponieważ nie mogę tego rozgryźć, znalazłem rozwiązanie online. ale naprawdę nie mogę zrozumieć, dlaczego to rozwiązanie działa albo ..SPOJ: wyjaśnienie rozwiązania M3TILE

zadaniem jest obliczenie na ile sposobów można to 3 * n (n >= 0, n jest tylko wejście) prostokąt być całkowicie wypełniona 2 * 1 domino.

np. (Czerwone linie oznaczają domino):

Image

To właśnie po raz pierwszy zwrócił na kartce papieru, gdy czytam teksty, i widziałem, że istnieją trzy możliwe kombinacje, że 3 * 2 prostokąt może mieć , a jeśli n jest nieparzyste, rozwiązaniem jest 0, ponieważ nie ma możliwości wypełnienia całego prostokąta (jeden element zawsze pozostanie odkryty przez domino).

Więc pomyślałem, że rozwiązanie było po prostu 3^n, jeśli n było parzyste, a 0, jeśli n było nieparzyste. Okazuje się, myliłem się.

znalazłem stosunkowo proste rozwiązanie tutaj:

#include <iostream> 

using namespace std; 

int main() 
{ 
    int arr[31]; 

    arr[0]=1; 
    arr[1]=0; 
    arr[2]=3; 
    arr[3]=0; 

    for(int i = 4; i < 31; i++) { 
     arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get 
    } 

    int n; 

    while(1) { 
     cin >> n; 

     if(n == -1) { 
      break; 
     } 

     cout << arr[n] << endl; 
    } 

    return 0; 
} 

Dlaczego to działa ?!

Odpowiedz

18

Niech T(n) będzie liczbą sposobów układania płytek 3×n za pomocą płytek 2×1. Ponadto, niech P(n) będzie liczbą sposobów układania płytki 3×n z jednym rogiem usuniętym z płytek 2×1. Załóżmy, że n jest wystarczająco duży (>= 4).

Następnie zastanów się, jak rozpocząć układanie od lewej (lub prawej, nie ma znaczenia).

Możesz umieścić kafelek pokrywający lewy górny róg na dwa sposoby, pionowo lub poziomo. Jeśli umieścić go w pozycji pionowej, dachówka obejmujący dolny lewy róg musi być umieszczony poziomo, dając konfigurację

| 
== 

To pozostawia P(n-1) sposoby na płytki pozostała część. Jeśli umieścisz go w poziomie, możesz umieścić kafelek pokrywający lewy dolny róg, poziomo lub pionowo. Jeśli umieścić go pionowo, jesteś w takiej samej sytuacji jak poprzednio, tylko odbicie, a jeśli go umieścić poziomo, należy umieścić płytki poziomo między nimi,

== 
== 
== 

zostawiając 3×(n-2) Nadzorczej do płytki.Zatem

T(n) = T(n-2) + 2*P(n-1)    (1) 

Teraz, biorąc pod uwagę płytę 3×(n-1) z jednym usunięte (już kryte) rogu (załóżmy górze po lewej), można umieścić płytki w pionie pod nim, dając

= 
| 

i pozostawiając cię z 3×(n-2) Nadzorczej do dachówki, czy można umieścić dwie płytki poziomo pod nim, dając

= 
== 
== 

i wtedy nie mają wyboru, aby umieścić kolejną płytkę ho rizontally na górze, dzięki czemu można

=== 
== 
== 

z 3×(n-3) pokładzie minus kącie

P(n-1) = T(n-2) + P(n-3) 

Sumując,

T(n) = T(n-2) + 2*(T(n-2) + P(n-3)) 
    = 3*T(n-2) + 2*P(n-3)       (2) 

Ale korzystając (1) z n-2 zamiast n, widzimy, że

T(n-2) = T(n-4) + 2*P(n-3) 

lub

2*P(n-3) = T(n-2) - T(n-4) 

wprowadzającą do (2) daje nawrotowi

T(n) = 4*T(n-2) - T(n-4) 

co było do okazania

+0

Nicea dowód! Więcej informacji dostępnych pod adresem http://oeis.org/A001835 –

+0

@Daniel Czy możesz wyjaśnić przypadek bazowy odpowiadający n = 0. –

+0

@ ATulSingh Dla n = 0, mamy tablicę bez komórek. Jest dokładnie jeden sposób na wyłożenie go: nie kładź na nim kafelków [deska 3 × 0 ma 3 · 0 = 0 komórek, więc potrzebujesz 0/(2 · 1) = 0/2 = 0 płytek]. –

0

start umieszczenie płytki z lewej i innego typu sub problemów skończyć się na pokazano na schemacie W każdym razie ja najpierw umieścić czerwone płytki następnie żółte płytki i zielonym Płytka jest w końcu umieszczona.

x (n) = x (n-2), 2 * r (n-1), z części (a), (b), (c)

r (n) = x (n- 1) + f (n-2) z przypadków (d), (e).

Możemy wyrazić f (n) pod względem x (n).

Spójrz na zdjęcie dalszych wyjaśnień

Tiles Problem - Image

Źródło: https://www.quora.com/Can-somebody-explain-solution-to-SPOJ-com-Problem-M3TILE