C#刷劍指Offer | 斐波那契數(shù)列
題目：寫一個(gè)函數(shù)，輸入n，求斐波那契（Fibonacci）數(shù)列的第n項(xiàng)。斐波那契數(shù)列的定義如下：
很多C/C++/C#/Java語(yǔ)言教科書在講述遞歸函數(shù)的時(shí)候，大多都會(huì)用Fibonacci作為例子，因此我們會(huì)對(duì)這種解法爛熟于心：
public static long FibonacciRecursively(uint n){if (n <= 0){return 0;}if (n == 1){return 1;}return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);}
上述遞歸的解法有很嚴(yán)重的效率問(wèn)題，通過(guò)求解第10項(xiàng)的調(diào)用過(guò)程圖來(lái)分析：
從上圖中不難發(fā)現(xiàn)：在這棵樹(shù)中有很多結(jié)點(diǎn)是重復(fù)的，而且重復(fù)的結(jié)點(diǎn)數(shù)會(huì)隨著n的增大而急劇增加，這意味計(jì)算量會(huì)隨著n的增大而急劇增大。事實(shí)上，用遞歸方法計(jì)算的時(shí)間復(fù)雜度是以n的指數(shù)的方式遞增的。
改進(jìn)的方法并不復(fù)雜。上述遞歸代碼之所以慢是因?yàn)橹貜?fù)的計(jì)算太多，我們只要想辦法避免重復(fù)計(jì)算就行了。這里的辦法是從下往上計(jì)算，首先根據(jù)f(0)和f(1)算出f(2)，再根據(jù)f(1)和f(2)算出f(3)……依此類推就可以算出第n項(xiàng)了。很容易理解，這種思路的時(shí)間復(fù)雜度是O(n)。
代碼實(shí)現(xiàn)
當(dāng)然是用我們最熟悉的C#代碼來(lái)實(shí)現(xià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;}
單元測(cè)試
代碼實(shí)現(xiàn)之后，我們需要寫一定的單元測(cè)試來(lái)驗(yàn)證我們的代碼實(shí)現(xiàn)。
[]public void FibonacciTest1(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(0),0);}[]public void FibonacciTest2(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(1), 1);}[]public void FibonacciTest3(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(2), 1);}[]public void FibonacciTest4(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(3), 2);}[]public void FibonacciTest5(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(4), 3);}[]public void FibonacciTest6(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(5), 5);}[]public void FibonacciTest7(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(6), 8);}[]public void FibonacciTest8(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(7), 13);}[]public void FibonacciTest9(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(8), 21);}[]public void FibonacciTest10(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(9), 34);}[]public void FibonacciTest11(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(10), 55);}[]public void FibonacciTest12(){Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(40), 102334155);
① 單元測(cè)試通過(guò)結(jié)果
② 代碼覆蓋率
?點(diǎn)擊獲取文章源碼