我一直在努力解决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;
}
为什么这项工作?
尼斯的证明!更多信息请访问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