文章目录
一、斐波那契数列的算法1.递归法2.一般算法
二、骨牌铺方格算法1.递归法2.一般算法
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块骨牌共有f(n)种摆放方法。 摆放最后一块有两种可能： 1.竖着放，那么前面n-1块就有f(n-1)种摆放方法； 2.横着放，那么前n-2块就有f(n-2)种摆放方法； 原理与斐波那契数列一样，n块骨牌共有f(n-1)+f(n-2)种摆放方法。
一、斐波那契数列的算法
1.递归法
int f(n
)
{
if(n
<=1)
return 1;
return f(n
-1)+f(n
-2)
}
此时有一个问题是，当n比较大时，使用上述递归法出现时间过长问题。 原因：很多问题被重复计算多次 eg: 解决方法 利用动态规划思想，把重复计算的问题存在表（数组）中。 代码如下：
long long int a
[50]={1,1,0};
long long int f(int n
)
{
if(a
[n
]>0) return a
[n
];
if(n
==0||n
==1)
return 1;
a
[n
]=f(n
-1)+f(n
-2);
return a
[n
];
}
2.一般算法
long long int a
[50]={1,1,0};
long long int f(int n
)
{
if(a
[n
]>0) return a
[n
];
if(n
==0||n
==1)
return 1;
a
[n
]=f(n
-1)+f(n
-2);
return a
[n
];
}
二、骨牌铺方格算法
1.递归法
#include<iostream>
#include<stdio.h>
using namespace std
;
long long int a
[100]={0,1,2,0};
long long int f(int n
)
{
if(a
[n
]>0)
return a
[n
];
if(n
<3)
return a
[n
];
a
[n
]=f(n
-1)+f(n
-2);
return a
[n
];
}
int main()
{
long long int n
;
long long int m
;
while(scanf("%lld",&n
)!=EOF)
{
m
=f(n
);
cout
<<m
<<endl
;
}
return 0;
}
在解决问题的过程中出现了很多小问题 1.一开始f()这个函数的返回值以及m的类型都没有定义成long long int 类型，导致当n=46甚至更大的数以后，出现了超限问题，导致最后得到的结果错误。 2.没有注意到题目中n是可以等于50的，在定义数组a的时候定义成a[50]，导致一直是Wrong Answer
2.一般算法
#include<stdio.h>
int main()
{
int i
,N
;
long long int x
[51]={0,1,2,3};
for(i
=4;i
<51;i
++)
x
[i
]=x
[i
-1]+x
[i
-2];
while(scanf("%d",&N
)!=EOF)
{
printf("%lld\n",x
[N
]);
}
return 0;
}
