題目描述
有一塊大小是 2 * n 的墻面，現(xiàn)在需要用2種規(guī)格的瓷磚鋪滿，瓷磚規(guī)格分別是 2 * 1 和 2 * 2，請計算一共有多少種鋪設的方法。
輸入
輸入的第一行包含一個正整數(shù)T（T<=20），表示一共有T組數(shù)據(jù)，接著是T行數(shù)據(jù)，每行包含一個正整數(shù)N（N<=30），表示墻面的大小是2行N列。
輸出
輸出一共有多少種鋪設的方法，每組數(shù)據(jù)的輸出占一行。

這道題是一道經(jīng)典的遞歸算法題，解題思路也很清晰。
做遞歸題目時，通常做法都是先看特殊情況與終止條件，再找遞推公式。這道題很明顯，當n=1是終止條件，n=2時候是特殊情況，原因是有兩種規(guī)格的瓷磚，當n=1推到n=2時候需要考慮到有22規(guī)格的瓷磚，而當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;
}
如果大家已經(jīng)會做這題了，可以拿一道新題練練手。兩題的解題方法是完全一樣的。
題目描述
小明最近新買了一個房間，為了給它做裝修，想要給它鋪上地磚。然而現(xiàn)有的地磚只有兩種規(guī)格分別為1米*1米、2米*2米，由于小明買的房間有點小，寬度只有3米，長度為N米。當然這樣一個房間也足夠他自己一個人住了。那么如果要給這個房間鋪設地磚，且只用以上這兩種規(guī)格的地磚，請問有幾種鋪設方案。
輸入
輸入的第一行是一個正整數(shù)C，表示有C組測試數(shù)據(jù)。接下來C行，每行輸入一個正整數(shù)n（1<=n<=30），表示房間的長度。
輸出
對于每組輸入，請輸出鋪設地磚的方案數(shù)目。
答案如下
http://www.itdecent.cn/p/1016716fc513