劍指offer之斐波那契數(shù)列

1 問(wèn)題

寫一個(gè)函數(shù)，輸入n,求斐波那契數(shù)列的第n項(xiàng)。斐波那契數(shù)列定義如下。

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


2 分析

1) 直接用遞歸

2) 我們用兩個(gè)變量保持每次需要計(jì)算下一個(gè)值得前面2個(gè)數(shù)，從最前面開始迭代。


 
3 代碼實(shí)現(xiàn)

    #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 運(yùn)行結(jié)果

    resultOne is 21
    resultTwo is 21
    
5 總結(jié)

方法二時(shí)間復(fù)雜度降低了很多，直接變成了O(n),比遞歸優(yōu)化了很多，當(dāng)我么求后面的結(jié)果需要前面的2個(gè)值的時(shí)候，后面的解需要依靠前面的解時(shí)候，我們可以用2個(gè)變量保持之前的值，然后每次算出一個(gè)新的值的時(shí)候進(jìn)行迭代更新這2個(gè)值，因?yàn)檫@里剛需只需要2個(gè)值，所以用2個(gè)變量就行，如果是剛需很多值的話，我們可以用數(shù)組進(jìn)行保持前面的值，后面的值就可以一一解答出來(lái)。




 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)