我一直在努力解决 this programming problem ,但由于我想不通,所以我在网上找到了解决方案。但我真的不明白为什么该解决方案也有效..
任务是计算一个 3*n(n >= 0
,n 是唯一的输入)矩形可以用多少种方法完全填充 2* 1 block 多米诺骨牌。
例如(红线代表多米诺骨牌):
这是我在看课文时首先在纸上画的,我看到一个 3*2 的矩形可以有三种可能的组合,如果 n 是奇数,则解为 0,因为有没有办法填满整个矩形(一 block 总是被多米诺骨牌覆盖)。
所以我认为解决方案很简单,如果 n 为偶数,则为 3^n
,如果 n 为奇数,则为 0
。事实证明,我错了。
我在这里找到了一个相对简单的解决方案:
#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;
}
为什么会这样?!
最佳答案
设 T(n)
是用 2×1
瓷砖拼贴 3×n
棋盘的方法数。此外,设 P(n)
是用 2×1
瓷砖移除一个角的 3×n
板的拼贴方式的数量.假设 n
足够大 (>= 4
)。
然后考虑如何从左侧(或右侧,无所谓)开始平铺。
您可以通过垂直或水平两种方式放置覆盖左上角的图 block 。如果竖着放,覆盖左下角的tile一定要横着放,给个配置
|
==
剩下 P(n-1)
种方式来平铺剩余部分。如果水平放置,则可以水平或垂直放置覆盖左下角的瓷砖。如果竖着放,就是和之前一样的情况,只是反射(reflect)而已,如果横着放,就必须在它们之间横着放一个tile,
==
==
==
留给您一 block 3×(n-2)
板来平铺。因此
T(n) = T(n-2) + 2*P(n-1) (1)
现在,考虑到 3×(n-1)
板有一个被移除(已经被覆盖)的角(假设左上角),您可以在其下方垂直放置一 block 瓷砖,给出
=
|
然后给你留下一个 3×(n-2)
的棋盘来拼贴,或者你可以在它下面水平放置两个拼贴,给出
=
==
==
然后你别无选择,只能在顶部水平放置另一个瓷砖,留下你
===
==
==
用 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)
但是,使用 (1)
和 n-2
代替 n
,我们看到了
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)
q.e.d.
关于c++ - 用 2 x 1 多米诺骨牌填充 3xN 瓷砖的方法数 (SPOJ : M3TILE),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16388579/