[数据结构与算法]C++实现斐波那契的三种方法

题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
做题链接：力扣–斐波那契数

1.法一：迭代

class Solution {
public:
    int fib(int n) {
        //1.迭代
        if(n==0)
        {
            return 0;
        }
        if(n==1)
        {
            return 1;
        }
        int first=1;
        int second=1;
        int third=1;
        n-=2;//按推算，n>2时，需要迭代n-2次得到第n个斐波那契数
        while(n)
        {
            third=(first+second)%(int)(1e9+7);//这里要注意取模，题目有提示
            first=second;
            second=third;
            n--;
        }
        return third;
    }
};

2. 法二：递归（简单版）

这个答案在牛客上可以通过，但是在力扣上过不了，当要求的第n个斐波那契数，n很大时，会超时。原因是因为在递归时计算了很多重复的值，比如计算fib(6)时，需要计算f(5)和f(4)，而计算f(5)时又要计算f(4)，所以时间消耗比较大。

class Solution {
public:
    int fib(int n) {
        //分治，递归
        if(n==0)
        {
            return 0;
        }
        if((n==1)||(n==2))
        {
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }
};

3.法三 递归（高效版）

使用容器map，首先查看需要的对应斐波那契数是否在map中，若有则直接拿出来使用，若没有再递归计算，同时插入map中，方便下一次使用。

class Solution {
private:
    unordered_map<int,int> filter;
public:
    int fib(int n) {
        //分治，递归
        if(n==0||n==1)
        {
            return n;
        }
        //找第n-1项数列值
        int pre=0;
        if(filter.find(n-1)==filter.end())//没找到
        {
            pre=fib(n-1);
            filter.insert({n-1,pre});
        }
        else//找到了
        {
            pre=filter[n-1];
        }

        //找第n-2项数列值
        int ppre=0;
        if(filter.find(n-2)==filter.end())
        {
            ppre=fib(n-2);
            filter.insert({n-2,ppre});
        }
        else
        {
            ppre=filter[n-2];
        }
        return (pre+ppre)%(int)(1e9+7);
    }
};