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

素颜马尾好姑娘i 2022-07-18 05:20 202阅读 0赞

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

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

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

![Center][]

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

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

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

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

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

#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];
    }</span>

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

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

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

/*
    时间复杂度：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;
     }</span>

（三）递归算法

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

/*
    时间复杂度：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);
    }</span>

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

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

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

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

[Center]: /images/20220717/00f55a7b373d47d28ad004999b0aeea3.png