SPOJ：M3TILE解決方案的解釋

我一直在努力解決this programming problem，但由於我無法弄清楚，我在網上找到了一個解決方案。但我不明白爲什麼這個解決方案仍然可以正常工作..SPOJ：M3TILE解決方案的解釋

任務是在多少種方法3 * N來計算（n >= 0，n是唯一的輸入）矩形是完全充滿了2 * 1多米諾骨牌。

例如（紅色線代表的多米諾骨牌）：

這是我第一次畫了一張紙，當我讀課文，我看到，有三種可能的組合，一個3 * 2矩形可以有，並且如果n是奇數，則解爲0，因爲沒有辦法填滿整個矩形，那麼（一塊將始終保持未被多米諾骨牌覆蓋）。

所以我認爲解決方案只是3^n，如果n是偶數，並且0，如果n是奇數。事實證明，我錯了。

我找到了一個相對簡單的解決方案在這裏：

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

爲什麼這項工作？

來源

2013-05-05 Abrf Kled

讓T(n)是可以平鋪一個3×n板的方式的數量，其中2×1平鋪。此外，讓P(n)是可以平鋪一塊牆板的方式的數量，其中一個牆板用2×1平鋪板移除。假設n足夠大（>= 4）。

然後考慮如何從左側（或右側，無所謂）開始平鋪。

您可以以兩種方式（垂直或水平）放置覆蓋左上角的瓷磚。如果你把它垂直，覆蓋左下角的瓷磚一定要橫放，給人一種配置

| 
==

這使得P(n-1)方式平鋪的剩餘部分。如果將其水平放置，則可以將水平或垂直放置在左下角的瓷磚上。如果垂直放置，你是在同樣的情況和以前一樣，只是反映了，如果你水平放置它，你必須水平放置它們之間的瓷磚，

== 
== 
==

留給你一個3×(n-2)板瓷磚。因此

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

現在，考慮到3×(n-1)板與一個刪除（已經覆蓋）一角（假設左上圖），你可以把垂直下方的瓷磚，給人

= 
|

並留下您用3×(n-2)板瓦片，或者你可以把兩塊地磚下面的水平吧，給

= 
== 
==

，然後你別無選擇，只能放置另一個瓦豪rizontally在上面，讓你

=== 
== 
==

與3×(n-3)板減去一個角落，

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

加起來，

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

但是，代替n使用(1)與n-2，我們看到

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

或

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

插入到這一點(2)產生復發

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

證明完畢

來源

2013-05-05 20:33:11

尼斯的證明！更多信息請訪問http://oeis.org/A001835 – 2013-05-05 20:40:32

@Daniel您能解釋一下對應於n = 0的基本情況嗎？ – 2014-08-03 10:25:04

@ATulSingh對於n = 0，我們有一個沒有細胞的板子。有一種方法可以將其平鋪：不在其上放置瓦片[3×0板上有3·0 = 0個單元，所以你需要0 /（2·1）= 0/2 = 0個瓦片。 – 2014-08-12 14:41:40

Sharing my image tut.Hope it helps .

來源

2015-12-16 08:24:30

請從鏈接添加一些內容。 – Robert 2015-12-16 08:59:15

@Robert你是什麼意思？ – 2015-12-16 09:57:21

如果未來鏈接中斷，則此答案變得多餘。 – Robert 2015-12-16 10:00:08

開始把磚從左邊和不同類型的你在顯示在圖中在任何情況下我第一次把紅瓦然後黃瓦結束了子問題和綠色瓷磚放在最後。

X（N）= X（N-2）+ 2 * F（N-1）從例（A），（B），（C）

F（N）= X（正1）+ f（n-2）來自病例（d），（e）。

我們可以用x（n）表示f（n）。

看圖像作進一步的解釋

Tiles Problem - Image

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

來源

2015-12-23 09:37:11 sanchitkum

SPOJ：M3TILE解決方案的解釋

回答

相關問題