学习用品

斐波那契数列

题目要求

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M

只是空行用

题目分析

斐波那契说白了就是一个递推关系。一说递推关系,一来想到的是递归,学过竞赛的,就会想到DP。其实本页面是以题目为切入,展示多种解。其中不乏一些大神的很妙的思路,来共同鉴赏学习。

只是空行用

代码

入门定义递归版

int Fibonacci(int n)
{
	if (n == 0) return 0; //特殊情况
	if (n <= 2) //递归出口
		return 1;
	else return Fibonacci(n - 1) + Fibonacci(n - 2);
}

递归优化版

int Fibonacci(int a, int b, int n)
{
	if (n == 0) return 0; //特殊情况
	else if (n > 2)
	{
		return Fibonacci(a + b, b, n - 1);
	}
	return a; //递归出口
}
//调用时,写作Fibonacci(1, 1, n);
//由于提前计算好了数列值,这种自底向上的算法可以减少递归次数

大神非递归DP版

int Fibonacci(int n)
{
	int f = 0, g = 1; //第0项和第1项
	while (n--)
	{
		g += f; //后项=前项+前前项 
		f = g - f; //前项=后项-前前项
		//由于f默认是第0项,所以在这里f比g滞后一项
	}
	return f;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注