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解决方案的解释

回答

相关问题