剑指offer之斐波那契数列

1 问题

写一个函数，输入n,求斐波那契数列的第n项。斐波那契数列定义如下。

    f(n) = 0; (n = 0)
     
    f(n) = 1; (n = 1)
     
    f(n) = f(n - 1) + f(n - 2); (n >= 2);


2 分析

1) 直接用递归

2) 我们用两个变量保持每次需要计算下一个值得前面2个数，从最前面开始迭代。


 
3 代码实现

    #include <stdio.h>
     
    long long fibonacciOne(unsigned int n)
    {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        return fibonacciOne(n - 1) + fibonacciOne(n - 2);
    }
     
    long long fibonacciTwo(unsigned int n)
    {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        long long first = 0;
        long long second = 1;
        long long sum = 0;
        for (int  i = 2; i <= n ; ++i)
        {
            sum = first + second;
            first = second;
            second = sum;
        }
        return sum;
    }
     
    int main(void)
    {
        long long resultOne = fibonacciOne(8);
        long long resultTwo = fibonacciTwo(8);
        printf("resultOne is %lld\n", resultOne);
        printf("resultTwo is %lld\n", resultTwo);
        return 0;
    }

 
4 运行结果

    resultOne is 21
    resultTwo is 21
    
5 总结

方法二时间复杂度降低了很多，直接变成了O(n),比递归优化了很多，当我么求后面的结果需要前面的2个值的时候，后面的解需要依靠前面的解时候，我们可以用2个变量保持之前的值，然后每次算出一个新的值的时候进行迭代更新这2个值，因为这里刚需只需要2个值，所以用2个变量就行，如果是刚需很多值的话，我们可以用数组进行保持前面的值，后面的值就可以一一解答出来。




 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)