1188: 零起点学算法95——骨牌铺方格（递归）

àì夳堔傛蜴生んèń 2022-10-25 05:45 220阅读 0赞

## Description ##

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.  
例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：  
![396f212ed2d31ef1fd2e921eb1b248b2.png][]

## Input ##

输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

## Output ##

对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。

## Sample Input ![5f8f312f51791b8bb0ed0ae07c2ffa43.gif][] ##

1
    3
    2

## Sample Output ##

1
    3
    2

## Source ##

[零起点学算法][Link 1]

## Code ##

应该是个递归？

觉得规律就是前两个的和等于第三个

#include<iostream>
    #include<stdio.h>
    using namespace std;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int a[59];
            a[1]=1;
            a[2]=2;
            for(int i=3;i<=n;i++)
                a[n]=a[n-1]+a[n-2];
            cout<<a[n]<<endl;
        }
    }

结果wa

想着可能是越界问题？果不其然

![20210131113434186.png][]

换成long long型

#include<iostream>
    #include<stdio.h>
    using namespace std;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            long long a[59];
            a[1]=1;
            a[2]=2;
            for(int i=3;i<=n;i++)
                a[n]=a[n-1]+a[n-2];
            cout<<a[n]<<endl;
        }
    }

[396f212ed2d31ef1fd2e921eb1b248b2.png]: /images/20221024/797122dd4a0d4d3195c7820060478a0e.png
[5f8f312f51791b8bb0ed0ae07c2ffa43.gif]: /images/20221024/931ac09ca2a7469e8b8c6e36b0850ea0.png
[Link 1]: https://oj.wustacm.top/problemset.php?search=%E9%9B%B6%E8%B5%B7%E7%82%B9%E5%AD%A6%E7%AE%97%E6%B3%95&searchmode=source&soj=0
[20210131113434186.png]: /images/20221024/90a9782e740149d5b2984ac4d9610bb9.png