記錄來(lái)自《劍指offer》的算法題。

題目如下：

寫(xiě)一個(gè)函數(shù)，輸入n，實(shí)現(xiàn)斐波那契數(shù)列的第n項(xiàng)。

斐波那契數(shù)列的定義如下：

f(n)=???01f(n?1)+f(n?2)n=0n=1n>1
教科書(shū)上通常在介紹遞歸的時(shí)候都會(huì)使用斐波那契數(shù)列作為例子，然后給出下列解法：

long long Fibonacci(unsigned int n){if(n<=0)return 0;if(n == 1)return 1;return Fibonacci(n-1) + Fibonacci(n-2); }

但這個(gè)算法在n的增大后會(huì)變得很慢，主要原因是重復(fù)的計(jì)算比較多，改進(jìn)算法如下所示：

// 改進(jìn)版本 long long FibonacciOptimz(unsigned int n){int result[2] = { 0, 1 };if (n < 2)return result[n];long long fibNMinusOne = 1;long long fibNMinusTwo = 0;long long fibN = 0;for (unsigned int i = 2; i <= n; i++){fibN = fibNMinusOne + fibNMinusTwo;fibNMinusTwo = fibNMinusOne;fibNMinusOne = fibN;}return fibN; } // 測(cè)試 int main(void){int n = 10;cout << "use Fibonacci(), n = " << n << ", result = " << Fibonacci(n) << endl;cout << "use FibonacciOptimz(), n = " << n << ", result = " << FibonacciOptimz(n) << endl;cout << "start to test:\n";int test[] = { 0, 1, 2, 3, 5, 10, 40, 50, 100 };for (int i = 0; i < 9; i++){int num = test[i];cout << "use FibonacciOptimz(), num = " << num << ", result = " << FibonacciOptimz(num) << endl;}system("pause");return 0; }

這種算法的時(shí)間復(fù)雜度是O(n)，它采用循環(huán)的方法，每次循環(huán)的時(shí)候都保存中間值，并用于下次的計(jì)算。

對(duì)于斐波那契數(shù)列的應(yīng)用，還有如下問(wèn)題：

一只青蛙一次可以跳上一級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

這個(gè)問(wèn)題也就是需要實(shí)現(xiàn)斐波那契數(shù)列。考慮最簡(jiǎn)單的情況，如果只有1級(jí)臺(tái)階，那顯然只有一種跳法；如果有2級(jí)臺(tái)階，則有兩種跳法，一次只跳1級(jí)和1次跳兩級(jí)臺(tái)階。現(xiàn)在討論一般情況，將n級(jí)臺(tái)階時(shí)的跳法看成是n的函數(shù)，記為f(n)。當(dāng)n>2時(shí)，第一次跳的時(shí)候有兩種選擇，一是第一次只跳1級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目，即f(n?1)；另一種選擇是第一次跳2級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-2級(jí)臺(tái)階的跳法數(shù)目，即為f(n?2)。因此n級(jí)臺(tái)階的不同跳法的總數(shù)f(n)=f(n?1)+f(n?2)，也就是斐波那契數(shù)列。

當(dāng)然，如果上述問(wèn)題的條件變成：青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)??它也可以跳上n級(jí)，問(wèn)跳上n級(jí)臺(tái)階總共有多少種跳法。通過(guò)數(shù)學(xué)歸納法可以得到f(n)=2n?1。

總結(jié)

以上是生活随笔為你收集整理的剑指offer--斐波那契数列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。