Problem Description

? ? 在2×n的一個長方形方格中,用一個1× 2的骨牌鋪滿方格,輸入n ,輸出鋪放方案的總數.

????例如n=3時,為2× 3方格，骨牌的鋪放方案有三種,如下圖：

????

Input

? ??輸入數據由多行組成，每行包含一個整數n,表示該測試實例的長方形方格的規格是2×n (0<n<=50)。

Output

? ??對于每個測試實例，請輸出鋪放方案的總數，每個實例的輸出占一行。

Sample Input

1 3 2

Sample Output

1 3 2

思路：

設：用a[i]表示2*i的方格的方法數

已知：

????a[1]=1;

????a[2]=2;

????a[3]=3;

則：

????a[i]實質是在2*（i-1）的格子后加上一格2*1的方格，骨牌在這一格上橫放或豎放。

????如果前面i-1塊已經鋪好，則第i塊只有豎著放；

????如果前面i-1塊已經鋪好，則第i塊只有橫著放。

?????????????????????????????????????????????????????????????????????????????????????????（圖源網絡 侵刪致歉）

簡單驗證：
? ? ? 規格為1時： 1種
? ? ? 規格為2時： 2種
? ? ? 規格為3時： 3種
? ? ? 規格為4時： 5種
? ? ? 規格為5時： 8種
? ? ? ? ? ? ? ?……
可推：第 n 個的可能路徑為 ?f(n)=f(n-1)+f(n-2)（斐波那契數列）

Source Program

#include<iostream> using namespace std; int main() {long long a[50];//注意用long longint n;int i;/*預處理，先求出斐波那契數列*/a[0]=1;a[1]=1;a[2]=2;for(i=3;i<=50;i++)a[i]=a[i-1]+a[i-2];while(cin>>n)cout<<a[n]<<endl;return 0; }

?

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的骨牌铺方格（HDU-2046）的全部內容，希望文章能夠幫你解決所遇到的問題。

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