题目

Description

问题描述:有2×n的一个长方形棋盘,用一些1×2的骨牌铺满方格.
例如:n=3时,在2×3的棋盘上用1×2的骨牌覆盖,共有3种铺法。
问题求解:编写一个程序,试对给出的任意一个n(n>0),输出铺法总数.

Input

输入包括多组数据，每组数据占一行，且只有一个整数n (0<=n<=42),表示2*n的棋盘,当n=0时表示输入结束。

Output

输出一行结果，为一个整数，表示棋盘完美覆盖方案数。

Sample Input

8
0

Sample Output

34

题解

显然,这道题可以使用某种神奇的数学规律来求解
先找下规律

n 1 2 3 4 5 6 7 8
num 1 2 3 5 8 13 21 34

就是斐波那契数列
f[n] = f[n-1] + f[n-2]

理解下原理
最后的方块只有两种情况:

  • 竖着放一列
  • 横着两个放两列

分别对应

  • 最后两列一个竖着放,考虑前面 n-1 列的情况( f[n-1] )
  • 最后两列全部竖着放,考虑前面 n-2 列的情况( f[n-2] )

因此,将两种情况加起来就是答案

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
const int maxn = 45;
int f[maxn] = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170};
void F(int i=2) {
    if(i == maxn)
        return;
    f[i] = f[i - 1] + f[i - 2];
    F(i + 1);
};
 
bool Do() {
    int n;
    scanf("%d",&n);
    if(n == 0)
        return false;
 
    printf("%d\n",f[n]);
 
    return true;
}
 
int main() {
    while(Do());
    return 0;
}