Tiling_easy version分析

俗话说得好，水水更健康，水水更开心。。。 然而水题不是那么好做的，呜呜。。。

递推是很多人的弱项，比如我。

Tiling_easy version

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7671 Accepted Submission(s): 5929

Problem Description

有一个大小是 2 x n 的网格，现在需要用2种规格的骨牌铺满，骨牌规格分别是 2 x 1 和 2 x 2，请计算一共有多少种铺设的方法。

Input

输入的第一行包含一个正整数T（T<=20），表示一共有 T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示网格的大小是2行N列。

Output

输出一共有多少种铺设的方法，每组数据的输出占一行。

Sample Input 3 2 8 12

Sample Output 3 171 2731

分析

n=1时，f(n)=1； n=2时，f(n)=3； n=3时，f(n)=5； …… 假设2*n个空间，已知a[n-1]和a[n-2]。(宽2，长n) (1)先把2*（n-1）放好，那么剩余的2*1的空间只能放一个竖放的2*1，这里有a[n-1]种 (2)、先把2*（n-2）放在空间的上方，那么剩余的2*2的空间可以放两个2*1，两个竖放的2*1，一个2*2,共3种，但是，注意的是，两个竖放的2*1这种情况与（1）的重复，so，只有两种情况符合，这里有2*a[n-2]种 so，a[n]=a[n-1]+2*a[n-2] 代码如下：

#include<stdio.h> int main() { long a[32]; int n, b; a[0] = 1; a[1] = 3; for (int i = 2; i < 31; i++) a[i] = a[i - 1] + 2 * a[i - 2]; while (scanf("%d", &n) == 1) { while (n--) { scanf("%d", &b); printf("%ld\n", a[b - 1]); } } return 0; }