题目描述
有一块大小是 2 * n 的墙面，现在需要用2种规格的瓷砖铺满，瓷砖规格分别是 2 * 1 和 2 * 2，请计算一共有多少种铺设的方法。
输入
输入的第一行包含一个正整数T（T<=20），表示一共有T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示墙面的大小是2行N列。
输出
输出一共有多少种铺设的方法，每组数据的输出占一行。
这道题是一道经典的递归算法题，解题思路也很清晰。
做递归题目时，通常做法都是先看特殊情况与终止条件，再找递推公式。这道题很明显，当n=1是终止条件，n=2时候是特殊情况，原因是有两种规格的瓷砖，当n=1推到n=2时候需要考虑到有22规格的瓷砖，而当n>2时候，观察一下增加一列如何求得铺的地砖，我的想法是，增加一列有分两种情况，若是之前铺瓷砖的方法不变，那铺设的方法就是f(n-1)，第二种情况之前的铺瓷砖的方式进行改变，如果是改两块瓷砖的铺设方法，那么就是f(n-2)，而如果是一个22的墙面，你可以用两种方法，一种是横着放两块瓷砖，一种是直接放一块2*2的瓷砖，注意 这里不是三种方法，因为直接竖着放两块瓷砖的方法其实是属于第一种情况的。
因此f(n-2)是需要乘2的，若是改三块瓷砖的铺设方法，那显然可以由之前的递归所得到。
因此递归公式就是 f(n)=f(n-1)+f(n-2)*2
最近在学C++，于是用C++完成该算法。
#include<iostream>
using namespace std;
int f(int n)
{
if(n==1) return 1;
if(n==2) return 3;
return f(n-1)+2*f(n-2);
}
int main()
{
int T;
cout<<"请输入T";
while(cin>>T,T>20)
{
cout<<"T小于20，请重新输入";
}
cout<<"请输入N";
int N;
for(int i=0;i<T;i++)
{
cin>>N;
cout<<f(N);
}
return 0;
}
如果大家已经会做这题了，可以拿一道新题练练手。两题的解题方法是完全一样的。
题目描述
小明最近新买了一个房间，为了给它做装修，想要给它铺上地砖。然而现有的地砖只有两种规格分别为1米*1米、2米*2米，由于小明买的房间有点小，宽度只有3米，长度为N米。当然这样一个房间也足够他自己一个人住了。那么如果要给这个房间铺设地砖，且只用以上这两种规格的地砖，请问有几种铺设方案。
输入
输入的第一行是一个正整数C，表示有C组测试数据。接下来C行，每行输入一个正整数n（1<=n<=30），表示房间的长度。
输出
对于每组输入，请输出铺设地砖的方案数目。
答案如下
https://www.jianshu.com/p/1016716fc513
