骨牌覆盖
tale.pascal/c/cpp
【题目描述】
给定一个2行n列的棋盘，用1*2的骨牌去完整覆盖，求方案数。
【输入】
输入仅包含一个数n。
【输出】
输出合法方案数模上1000000007。
【输入样例】
3
【输出样例】
3
【样例解释】
000
000 表示一个长度为3，宽度为2的棋盘，有如下三种覆盖方式
112
332
123
123
122
133
1~3的数字分别表示三块不同骨牌的摆放
注意：骨牌是不加以区分的，也就是说
112
332
和
113
223 被认为是同一种情况。
【数据规模】
对于20%的数据，n<5
对于所有数据，n<=100000
解析：把n等于1,2,3,4,5,6,7的情况算出，依次是1,2,3,5,8,13,21，可以看出数列是遵循斐波那契数列规律的，可有如何证明呢？
我们用f[i]表示用i块骨牌有多少种情况，那么，可以根据最后一块骨牌的放置情况分类，当最后一块骨牌是竖直放置时，有f[i-1]种情况，1最后一块木块是横置时，倒数第二块木块也只能横置，所以有有f[i-2]种情况。综上：f[i]=f[i-1]+f[i-2],符合斐波那契数列规律，初始f[1]=1,f[2]=2.
代码见：
C++
#include<cstdio>
#include<cstdlib>
using namespacestd;
void init()
{
freopen("tale.in","r",stdin);
freopen("tale.out","w",stdout);
}
void work()
{
int n,i,x,y,z;
scanf("%d",&n);
if(n==1){printf("%d\n",1);exit(0);}
if(n==2){printf("%d\n",2);exit(0);}
x=1;y=2;
for(i=3;i<=n;i++)
{
z=(x+y)%1000000007;
x=y;y=z;
}
printf("%d\n",z);
//while(1);
}
int main()
{
init();
work();
return 0;
}
Pascal
procedure init;
begin
assign(input,'tale.in');
assign(output,'tale.out');
reset(input);
rewrite(output);
end;
procedure terminate;
begin
close(input);
close(output);
halt;
end;
procedure main;
var
n,i,x,y,z:longint;
begin
read(n);
if n=1 then
begin
writeln(1);
termiante;
end;
if n=2 then
begin
writeln(2);
terminate;
end;
x:=1;y:=2;
for i:=3 to n do
begin
z:=(x+y) mod 1000000007;
x:=y; y:=z;
end;
writeln(z);
end;
begin
init；
main;
terminate;
end.