劍指Offer面試題：8.斐波那契數列

題目：寫一個函數，輸入n，求斐波那契（Fibonacci）數列的第n項。很多C/C++/C#/Java語言教科書在講述遞歸函數的時候，大多都會用Fibonacci作為例子，因此我們會對這種解法爛熟于心。但是，上述遞歸的解法有很嚴重的效率問題，通過求解第10項的調用過程圖來分析，在這棵樹中有很多結點是重復的，而且重復的結點數會隨著n的增大而急劇增加，這意味計算量會隨著n的增大而急劇增大。

一、題目：斐波那契數列

題目：寫一個函數，輸入n，求斐波那契（Fibonacci）數列的第n項。斐波那契數列的定義如下：　

二、效率很低的解法

　　很多C/C++/C#/Java語言教科書在講述遞歸函數的時候，大多都會用Fibonacci作為例子，因此我們會對這種解法爛熟于心：

    public static long FibonacciRecursively(uint n)
    {
        if (n <= 0)
        {
            return 0;
        }
        if (n == 1)
        {
            return 1;
        }

        return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);
    }

　　上述遞歸的解法有很嚴重的效率問題，通過求解第10項的調用過程圖來分析：

　　從上圖中不難發現：在這棵樹中有很多結點是重復的，而且重復的結點數會隨著n的增大而急劇增加，這意味計算量會隨著n的增大而急劇增大。事實上，用遞歸方法計算的時間復雜度是以n的指數的方式遞增的。

三、實用循環的解法

　　改進的方法并不復雜。上述遞歸代碼之所以慢是因為重復的計算太多，我們只要想辦法避免重復計算就行了。這里的辦法是從下往上計算，首先根據f(0)和f(1)算出f(2)，再根據f(1)和f(2)算出f(3)……依此類推就可以算出第n項了。很容易理解，這種思路的時間復雜度是O(n)。

    public static long FibonacciIteratively(uint n)
    {
        int[] result = { 0, 1 };
        if (n < 2)
        {
            return result[n];
        }

        long fibNMinusOne = 1;
        long fibNMinusTwo = 0;
        long fibN = 0;

        for (uint i = 2; i <= n; i++)
        {
            fibN = fibNMinusOne + fibNMinusTwo;

            fibNMinusTwo = fibNMinusOne;
            fibNMinusOne = fibN;
        }

        return fibN;
    }

四、單元測試

　　（1）單元測試用例

    [TestMethod]
    public void FibonacciTest1()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(0),0);
    }

    [TestMethod]
    public void FibonacciTest2()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(1), 1);
    }

    [TestMethod]
    public void FibonacciTest3()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(2), 1);
    }

    [TestMethod]
    public void FibonacciTest4()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(3), 2);
    }

    [TestMethod]
    public void FibonacciTest5()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(4), 3);
    }

    [TestMethod]
    public void FibonacciTest6()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(5), 5);
    }

    [TestMethod]
    public void FibonacciTest7()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(6), 8);
    }

    [TestMethod]
    public void FibonacciTest8()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(7), 13);
    }

    [TestMethod]
    public void FibonacciTest9()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(8), 21);
    }

    [TestMethod]
    public void FibonacciTest10()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(9), 34);
    }

    [TestMethod]
    public void FibonacciTest11()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(10), 55);
    }

    [TestMethod]
    public void FibonacciTest12()
    {
        Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(40), 102334155);
    }