題目描述

有一塊大小是 2 * n 的墻面，現在需要用2種規格的瓷磚鋪滿，瓷磚規格分別是 2 * 1 和 2 * 2，請計算一共有多少種鋪設的方法。

輸入

輸入的第一行包含一個正整數T(T<=20)，表示一共有T組數據，接著是T行數據，每行包含一個正整數N(N<=30)，表示墻面的大小是2行N列。

輸出

輸出一共有多少種鋪設的方法，每組數據的輸出占一行。

樣例輸入 Copy

3

2

8

12

樣例輸出 Copy

3

171

2731

思路：這是一道遞歸題，主要要找到遞歸規律，但是我笨！我找不到

參考：https://www.jianshu.com/p/253d948b2bb3

動態規劃法，但是我輸出超限了：https://blog.csdn.net/weixin_43207025/article/details/89602338

做遞歸題目時，通常做法都是先看特殊情況與終止條件，再找遞推公式。這道題很明顯，當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

#include

#include

#include

using namespace std;

int f(int x)

{

if(x==1)

{

return 1;

}

if(x==2)

{

return 3;

}

return f(x-1)+2*f(x-2);//知道這個規律那還不簡單？

}

int main()

{

int n;

cin >> n;

while(n--)

{

int m;

cin >> m;

cout << f(m) <

}

return 0;

}

標簽：15,遞歸,int,C語言,瓷磚,鋪設,include,方法

來源： https://www.cnblogs.com/FantasticDoubleFish/p/14315356.html

總結

以上是生活随笔為你收集整理的c语言一行黑白相间的瓷砖,C语言编程练习15：贴瓷砖的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。