实现斐波那契数列的三种方法

ktpd

斐波那契数列又称黄金分割数列。它的特点是从第3个数开始，每一个数都等于前面两个数相加。

例：0   1   1   2   3   5   8   13   21.。。。。。

从上我们可以总结出以下规律:

                    

当n =  0时； F(n) = 0;

当n = 1时； F(n) = 1;

当n > 1时；  F(n) = F(n-1)+F(n-2);

那我们如何求出这个数列中第n个数是多少呢？

（一）以指针实现斐波那契数列

[C++] 纯文本查看 复制代码

#include<iostream>
#include<cassert>
using namespace std;
/*
时间复杂度：O(N)
空间复杂度：0(N)
*/
long long Fib(long long  n)//当n = 30时，斐波那契数已经很大了，所以我们把类型定义为long long
{
	assert(n >= 0);//n必须大于0
	if(n==0||n==1)
	{
		return n;
	}
	// 建立一个指针，并为该指针开辟空间
	//因为数列最开始有一个0，所以当我们求第n个数的时候，需要多开劈一个空间
	long long *p = new long long[n+1];
	p[0] = 0;
	p[1] = 1;
	for(int i = 2;i < n+1; i++)
	{
		//从下标为2的数开始，每个数都等于它前面两个数相加
		p[i] = p[i-1]+p[i-2];
	}
	//返回要找的第n个数
	return p[n];
}

（二）交替相加法（我自己起的名字）

建立一个first变量，一个second变量，一个third变量。third = first + second。

每加完一次，都把first的值置成second，把second置成third。得到新的两个变量，然后求取新的third。

[C++] 纯文本查看 复制代码

/*
时间复杂度：O(N)
空间复杂度：0(1)
*/
//省略了头文件，全局命名空间
 long long Fib(long long  n)
 {
	assert(n >= 0);
	if(n==0||n==1)
	{
		return n;
	}
	long long first = 0;
	long long second = 1;
	long long third = 0;
	for(int i = 2;i<=n;i++)
	{
		third = first+second; 
		first = second;//将second的值赋给first
		second = third;//将third的值赋给second
	}
	return third;
 }

（三）递归算法

这三个算法中，递归可谓是最简单的也是最难理解的。我们先看代码：

[C++] 纯文本查看 复制代码

/*
时间复杂度：O(2^N)
空间复杂度：O(N)
*/
//省略了头文件，全局命名空间
long long Fib(long long  n)
{
	assert(n>=0);
	if(n == 1||n == 0)
	{
		return n;
	}
	return Fib(n-1)+Fib(n-2);
}

这个递归的终止条件是 n==1 或 n == 2 。

当我们传进去的n大于这两个数的时候，这个程序对执行

• [C++] 纯文本查看 复制代码

  return Fib(n-1)+Fib(n-2);

  
  

递归进入下一层，直到满足终止条件。再一层一层返回。最后返回我们想要的值。

dxdeng

挺复杂的东西呢

CrestKing

这个我上竞赛培优的时候算过，特征根方程就ok了

卷翼

楼主学c++的？一起交流学习啊，感觉第二种方法最好，递归最差