POJ1953,斐波拉契数列

 

 与这道题极其相似的一道题，POJ2506http://124654439.iteye.com/admin/blogs/2071852

题目大意：

给一个n位的二进制数，求它有多少种不包含连续的一的排列，例如 n = 3时，有5种排列 ( 000, 001, 010, 100, 101)(011, 110, 111 中有连续的1所以不满足).。

分析:

我们先填n位二进制数的第一位，第一位有两种情况，1或0，当第一位为0时，这个n位数的排列数与其后的n-1位排列数相同，当第一位为1时，第二位一定为0（因为不能有连续的1），所以这个n位数的排列，与其后n-2 位数排列相同

所以我们可以得到一个公式 f(n)=f(n-1)+f(n-2)。即斐波拉契数列

有了这个公式我们很容易得到程序。不过需要注意的是，这道题用递归的方法会超时

#include<iostream>
using namespace std;
int main()
{
	int num;
	int n;
	int f[100];
	f[0]=1;
	f[1]=2;
	cin>>num;
	for(int k=1;k<=num;k++)
	{
		cin>>n;
		for(int i=2;i<=n;i++)
		{
			
			f[i]=f[i-1]+f[i-2];
		}
		cout<<"Scenario #"<<k<<":"<<endl;
		cout<<f[n]<<endl;
		cout<<endl;//这里根据题目格式要求还要输入一个换行
	}
	
	return 0;
}

 

 

评论

1 楼 金R在奋斗着 2014-05-27  

                   
表情帝应该是这样的好不好