题目大意:

问用 1212 的多米诺骨牌覆盖 3n3n 的矩形区域,总共有多少种不同的覆盖方式? 下图是矩形大小为 312312 的一个有效覆盖。

输入

有若干组输入,每组输入为一个整数 n,(0<=n<=30)n,(0<=n<=30) 。最后一个输入为 -1 ,表示输入结束。

输出

对于每组输入,输出一个整数,表示总共可能的覆盖个数。

样例输入

1
2
3
4
2
8
12
-1

样例输出

1
2
3
3
153
2131

题目分析

如果矩形区域为 2n2n,很容易找到递推公式 F[n]={1,if n = 0 or n = 1F[n1]+F[n2],if n > 1 现在矩形区域为 3n,递归关系似乎不太容易推导,但是只要坚持下去,还是可以找到递推关系的。 假设总的覆盖情况有 A[n]种,我们先找第一层底递推关系。 这里出现了一种新的情况 B[n],我们还无法表示,需要继续往下推导,直到找到递归式为止。

这样我们就找到了2组递推关系: {A[n]=2B[n1]+A[n2]B[n]=A[n1]+B[n2] 然后,只要找到初始情况 A[n]B[n] 的值,就可以递推求解了。 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

#define MAX_SIZE 32

int main() {
int n = 0;
int a[MAX_SIZE] = {1, 0, 3};
int b[MAX_SIZE] = {0, 1, 0};

for (int i = 3; i < MAX_SIZE; i++) {
a[i] = 2*b[i-1] + a[i-2];
b[i] = a[i-1] + b[i-2];
}
while (scanf("%d", &n) > 0) {
if (n < 0) {
break;
}
printf("%d\n", a[n]);
}
return 0;
}

题目网址:http://poj.org/problem?id=2663