骨牌铺方格

此博客链接：https://www.cnblogs.com/ping2yingshi/p/12409829.html

骨牌铺方格（65min)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2046

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

题解：

         方法：斐波那契运用。

         思路：此题一开始由题目图形可以特别容易得到n=1时，骨牌等于1，n=2时，骨牌等于2，而后面的骨牌有两种放法，要不竖着放，要不骨牌横着放，当n=i时，有两种情况，第一种情况：竖着放，这说明前面n-1块已经放好了，只差一块骨牌，第二种情况：横着放，这说明前面n-2块的骨牌已经排好。

  所以当n=i时情况等于前面n=i-1加上n=i-2这两种情况的和即num[i] = num[i - 1] + num[i - 2];

注意：

        1.数组定义int类型时当n超过44时，结果超出整型范围，所以要定义大一点的数据类型。

        2.数组定义大小时，注意时51不是50，这里我耗了好长时间猜找出错误，血的教训，看清数据范围。

代码如下：

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    int n;
    _int64 num[50] = { 0 };
    while (~scanf_s("%d",&n))
    {
  
        num[1] = 1;
        num[2] = 2;
        for (int i = 3; i <= n; i++)
        {
            num[i] = num[i - 1] + num[i - 2];
        }
        printf("%I64u
", num[n]);

    }
    return 0;
        
}