1059: 貼瓷磚

題目描述
有一塊大小是 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







最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末帮孔,一起剝皮案震驚了整個濱河市雷滋,隨后出現的幾起案子,更是在濱河造成了極大的恐慌文兢,老刑警劉巖晤斩,帶你破解...
    沈念sama閱讀 218,204評論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現場離奇詭異姆坚,居然都是意外死亡澳泵,警方通過查閱死者的電腦和手機,發(fā)現死者居然都...
    沈念sama閱讀 93,091評論 3 395
  • 文/潘曉璐 我一進店門兼呵,熙熙樓的掌柜王于貴愁眉苦臉地迎上來兔辅,“玉大人,你說我怎么就攤上這事击喂∥Γ” “怎么了?”我有些...
    開封第一講書人閱讀 164,548評論 0 354
  • 文/不壞的土叔 我叫張陵懂昂,是天一觀的道長介时。 經常有香客問我,道長凌彬,這世上最難降的妖魔是什么沸柔? 我笑而不...
    開封第一講書人閱讀 58,657評論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮铲敛,結果婚禮上褐澎,老公的妹妹穿的比我還像新娘。我一直安慰自己伐蒋,他們只是感情好乱凿,可當我...
    茶點故事閱讀 67,689評論 6 392
  • 文/花漫 我一把揭開白布顽素。 她就那樣靜靜地躺著,像睡著了一般徒蟆。 火紅的嫁衣襯著肌膚如雪胁出。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,554評論 1 305
  • 那天段审,我揣著相機與錄音全蝶,去河邊找鬼。 笑死寺枉,一個胖子當著我的面吹牛抑淫,可吹牛的內容都是我干的。 我是一名探鬼主播姥闪,決...
    沈念sama閱讀 40,302評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼始苇,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了筐喳?” 一聲冷哼從身側響起催式,我...
    開封第一講書人閱讀 39,216評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎避归,沒想到半個月后荣月,有當地人在樹林里發(fā)現了一具尸體,經...
    沈念sama閱讀 45,661評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡梳毙,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,851評論 3 336
  • 正文 我和宋清朗相戀三年哺窄,在試婚紗的時候發(fā)現自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片账锹。...
    茶點故事閱讀 39,977評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡萌业,死狀恐怖,靈堂內的尸體忽然破棺而出奸柬,到底是詐尸還是另有隱情咽白,我是刑警寧澤,帶...
    沈念sama閱讀 35,697評論 5 347
  • 正文 年R本政府宣布鸟缕,位于F島的核電站,受9級特大地震影響排抬,放射性物質發(fā)生泄漏懂从。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,306評論 3 330
  • 文/蒙蒙 一蹲蒲、第九天 我趴在偏房一處隱蔽的房頂上張望番甩。 院中可真熱鬧,春花似錦届搁、人聲如沸缘薛。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,898評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽宴胧。三九已至漱抓,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間恕齐,已是汗流浹背乞娄。 一陣腳步聲響...
    開封第一講書人閱讀 33,019評論 1 270
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留显歧,地道東北人仪或。 一個月前我還...
    沈念sama閱讀 48,138評論 3 370
  • 正文 我出身青樓,卻偏偏與公主長得像士骤,于是被迫代替她去往敵國和親范删。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,927評論 2 355

推薦閱讀更多精彩內容