SPOJ: spiegazione soluzione M3TILE

Question

Ho cercato di risolvere this programming problem, ma poiché non riesco a capirlo, ho trovato una soluzione online. ma non riesco davvero a capire perché questa soluzione funziona sia ..

il compito è quello di calcolare in quanti modi può un 3 * n (n >= 0, n è l'unico ingresso) rettangolo essere completamente riempiti con 2 * 1 domino.

ad es. (Linee rosse rappresentano domino):

Questo era quello che ho disegnato su un foglio di carta quando ho letto il testo, e ho visto che c'erano tre possibili combinazioni che un rettangolo 3 * 2 può avere e che se n è dispari la soluzione è 0 perché non c'è modo di riempire l'intero rettangolo (un pezzo rimarrà sempre scoperto da un domino).

Quindi ho pensato che la soluzione fosse semplicemente 3^n, se n era pari, e 0, se n era dispari. risulta, ho sbagliato.

Ho trovato un soluzione relativamente semplice qui:

#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; 
} 

Perché fa questo lavoro ?!

Answer 1

Lascia che sia T(n) il numero di modi in cui è possibile affiancare una scheda 3×n con le tessere 2×1. Inoltre, sia P(n) il numero di modi in cui è possibile affiancare una scheda 3×n con un angolo rimosso con i riquadri 2×1. Assumere n sufficientemente grande (>= 4).

Quindi considera come è possibile avviare la piastrellatura da sinistra (o destra, non importa).

È possibile posizionare la piastrella che copre l'angolo in alto a sinistra in due modi, verticale o orizzontale. Se lo si inserisce in verticale, superficie del rivestimento in basso a sinistra deve essere posizionato in orizzontale, dando una configurazione

| 
== 

che lascia P(n-1) modi per piastrelle la parte rimanente. Se lo si posiziona orizzontalmente, è possibile posizionare la piastrella che copre l'angolo in basso a sinistra in orizzontale o in verticale. Se lo si posiziona verticalmente, ci si trova nella situazione di prima, solo riflessa, e se lo si inserisce in orizzontale, è necessario inserire una tessera orizzontalmente tra loro,

== 
== 
== 

lasciando con un 3×(n-2) bordo per piastrelle.Così

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

Ora, considerando la scheda 3×(n-1) con uno rimosso angolo (già coperto) (supponiamo in alto a sinistra), è possibile inserire una tessera in verticale sotto di essa, dando

= 
| 

e lasciandovi con un 3×(n-2) bordo per piastrelle, o è possibile inserire due tessere in orizzontale sotto di esso, dando

= 
== 
== 

e quindi non hai scelta, ma di inserire un'altra tessera ho rizontally in alto, lasciando

=== 
== 
== 

con una scheda 3×(n-3) meno un angolo,

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

Sommando,

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

Ma, usando (1) con n-2 al posto di n, vediamo che

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

o

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

inserimento che in (2) cede il ripetersi

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

come volevasi dimostrare

Answer 2

Sharing my image tut.Hope it helps .

Answer 3

iniziare a posizionare le piastrelle da sinistra e il diverso tipo di problemi secondari si finisce a sono mostrati nel diagramma In ogni caso i primo posto la tessera rossa tegola poi giallo e il verde la tessera è finalmente posta.

x (n) = x (n-2) + 2 * f (n-1) da casi (a), (b), (c)

f (n) = x (n- 1) + f (n-2) dai casi (d), (e).

Possiamo esprimere f (n) in termini di x (n).

guardare l'immagine per ulteriori spiegazioni

Tiles Problem - Image

Fonte: https://www.quora.com/Can-somebody-explain-solution-to-SPOJ-com-Problem-M3TILE