骨牌铺方格

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 64114    Accepted Submission(s): 31045

 

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

 解题思路:

百度了一下,网上的思路都是一致的,如下:

1).先铺前n-1行,则有f(n-1)种方法,对于第n行,则只有横着铺一种方法,方法数为f(n-1)

2).先铺前n-2行,则有f(n-2)种方法,对于第n-1行和第n行,如果两个都横着铺则和1)中铺的方法有重复,所以只能竖着铺,方法数为f(n-2)

所以递推公式:f(n)=f(n-1)+f(n-2) ,会惊奇的发现,这就是斐波那契数列。

ac代码:

#include <iostream>
#define ll long long int
using namespace std;
ll a[55];
int main()
{
    ll n;
    a[1]=1;
    a[2]=2;
    while(scanf("%lld",&n)!=EOF)
    {
            for(ll i=3;i<=n;i++)
                a[i]=a[i-1]+a[i-2];
            printf("%lld\n",a[n]);
    }
    return 0;
}

注意:int的最大值大概是2e+9,(2147483647即2^31-1)a[46]=a[45]+a[44],a[46]已经超过了int的范围,所以要用long long ,舍弃int吧!!!要不然就会莫名其妙的WA!!!


晚安zzZZ,明天早上还有英语课~

拓展:

有1×n的一个长方形,用1×1、1×2、1×3的骨牌铺满方格。例如当n=3时为1×3的方格(如图),此时用1×1,1×2,1×3的骨牌铺满方格,共有四种铺法。

同理可以分析,先铺前n-1个格子,总的方法数为f(n-1)

先铺前n-2个格子,总的方法数为f(n-2)

先铺前n-3个格子,总的方法数为f(n-3)

所以f(n)=f(n-1)+f(n-2)+f(n-3)