剑指offer（7）——C++实现菲波那切数列

蔚落 2021-10-29 08:54 230阅读 0赞

# 题目 #

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

# 考察点 #

*  菲波那切数列：

f ( x ) = \{ 0 , n = 0 1 , n = 1 f ( n − 1 ) + f ( n − 2 ) , n > 1 f(x)=\\left\\\{ \\begin\{aligned\} &0, n=0 \\\\ &1, n=1 \\\\&f(n-1)+f(n-2),n>1 \\end\{aligned\} \\right. f(x)=⎩⎪⎨⎪⎧0,n=01,n=1f(n−1)\+f(n−2),n>1

*  循环与递归

# 解题思路 #

# 完整代码 #

## 递归实现 ##

class Solution {
        
    public:
        int Fibonacci(int n) {
        
            if(n==0)return 0;
            if(n==1)return 1;
            return Fibonacci(n-1)+Fibonacci(n-2);     
        }
    };

显示结果如下：  
![在这里插入图片描述][20190815145037356.png]  
出现该情况的原因不是程序有问题，而是当数据量过大时，递归方法计算的时间复杂度以n的指数方式递增。  
也就是说，递归虽然简洁，但因为它是函数调用自身，这是要消耗时间和空间的，并且可能会导致调用栈溢出的问题。

## 循环实现及完整代码 ##

/*07-斐波那切数列*/
    #include<iostream>
    using namespace std;
    class Solution {
        
    public:
    	int Fibonacci_iter(int n) //迭代实现
    	{
        
    		if (n == 0) return 0;
    		if (n == 1) return 1;
    		return Fibonacci_iter(n - 1) + Fibonacci_iter(n - 2);
    	}
    	int Fibonacci(int n)// 循环实现
    	{
        
    		if (n == 0) return 0;
    		if (n == 1) return 1;
    		int result = 0;
    		int one = 0;
    		int two = 1;
    		for (int i = 2; i <= n; i++)
    		{
        
    			result = one + two;
    			one = two;
    			two = result;
    		}
    		return result;
    	}
    };
    int main()
    {
        
    	Solution s;
    	cout << s.Fibonacci_iter(2) << endl;
    	cout << s.Fibonacci(3) << endl;
    	return 0;
    }

# 编程时出现的问题 #

*  总是把`==`写成 `=`

[20190815145037356.png]: /images/20211029/4fc953189c25450c9aa0503597063bb5.png