題目描述
有一塊大小是 2 * n 的墻面,現在需要用2種規(guī)格的瓷磚鋪滿,瓷磚規(guī)格分別是 2 * 1 和 2 * 2,請計算一共有多少種鋪設的方法。
輸入
輸入的第一行包含一個正整數T(T<=20)映企,表示一共有T組數據,接著是T行數據静浴,每行包含一個正整數N(N<=30)堰氓,表示墻面的大小是2行N列。
輸出
輸出一共有多少種鋪設的方法苹享,每組數據的輸出占一行双絮。
這道題是一道經典的遞歸算法題浴麻,解題思路也很清晰。
做遞歸題目時囤攀,通常做法都是先看特殊情況與終止條件软免,再找遞推公式。這道題很明顯焚挠,當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;
}
如果大家已經會做這題了擦盾,可以拿一道新題練練手嘲驾。兩題的解題方法是完全一樣的。
題目描述
小明最近新買了一個房間迹卢,為了給它做裝修辽故,想要給它鋪上地磚。然而現有的地磚只有兩種規(guī)格分別為1米*1米腐碱、2米*2米誊垢,由于小明買的房間有點小,寬度只有3米,長度為N米喂走。當然這樣一個房間也足夠他自己一個人住了殃饿。那么如果要給這個房間鋪設地磚,且只用以上這兩種規(guī)格的地磚芋肠,請問有幾種鋪設方案乎芳。
輸入
輸入的第一行是一個正整數C,表示有C組測試數據帖池。接下來C行奈惑,每行輸入一個正整數n(1<=n<=30),表示房間的長度碘裕。
輸出
對于每組輸入携取,請輸出鋪設地磚的方案數目。
答案如下
http://www.reibang.com/p/1016716fc513