前陣子，日劇“輪到你了”終于大結(jié)局了，雖然結(jié)局有點(diǎn)一言難盡，但黑島和二階堂兩個(gè)學(xué)霸之間的愛情，還是很甜呢吶！兩個(gè)學(xué)霸之間的默契的斐波那契數(shù)列也被許多網(wǎng)友認(rèn)為是兇手行兇的依據(jù)。到底這數(shù)列有啥神奇之處，又該如何使用代碼實(shí)現(xiàn)呢？一起往下看吧！斐波那契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：1，1，2，3，5，8，13，21，34，55……?我們不難發(fā)現(xiàn)從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。以遞歸的方法定義就是F0=0，F1=1，Fn=Fn-1+Fn(n>=2，n∈N*)。(為了與數(shù)組下標(biāo)的概念對應(yīng)，F0為第0項(xiàng))。通過上面的解釋，相信你對斐波那契數(shù)列有一定的了解了吧，那我們來看看今天的題目吧。今天的題目就是：當(dāng)你輸入一個(gè)整數(shù)n后，輸出斐波那契數(shù)列的第n項(xiàng)(從0開始，第0項(xiàng)為0，n<=39)。腦袋里有什么想法了么？沒有的話來看看下面的三種解法吧。一、遞歸解法斐波那契數(shù)列具有天然的遞歸性,根據(jù)數(shù)學(xué)上的定義，可以得出其遞推公式為:Fn=Fn-1+Fn-2(n>=2，n∈N*),基礎(chǔ)情況為 F0=1,F1=1。對于遞歸解法，我們可以把問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題,找出明確的不需要繼續(xù)進(jìn)行遞歸的條件(即基本情況base case)，在本題中的基本情況為F0=0,F1=1, 當(dāng)遞歸至基本情況后,無需繼續(xù)遞歸，最后把子問題的解匯聚成大問題的解。可畫遞歸樹解決遞歸問題public?class?Solution?{ public int Fibonacci(int n) { //base case if (n==0){ return 0; } if(n==1){ return 1; } return Fibonacci(n-1)+Fibonacci(n-2); }}復(fù)雜度分析:

①子問題個(gè)數(shù)，即遞歸樹中節(jié)點(diǎn)的總數(shù)，而二叉樹節(jié)點(diǎn)總數(shù)為指數(shù)級別，所以子問題個(gè)數(shù)為 O(2^n)；而解決一個(gè)子問題的時(shí)間，在本算法中，沒有循環(huán)，只有 f(n - 1) + f(n - 2)f(n?1)+f(n?2) 一個(gè)加法操作，所以時(shí)間為O(1)。故我們可以得到這個(gè)算法的時(shí)間復(fù)雜度為 O(2^n),指數(shù)級別。

②而在遞歸過程中,需要在存儲遞歸過程中的運(yùn)算結(jié)果,最大空間為樹的高度h(即n)，而時(shí)間復(fù)雜度:O(2^n)，故空間復(fù)雜度:O(h) 即O(n)。問題分析:觀察遞歸樹，很明顯發(fā)現(xiàn)了算法低效的原因：存在大量重復(fù)計(jì)算，運(yùn)算的規(guī)模與n的大小成指數(shù)關(guān)系，因此這個(gè)暴力遞歸算法雖然簡潔明了,但運(yùn)行效率低下。二、動態(tài)分析由于暴力遞歸存在大量的重復(fù)運(yùn)算,降低了算法的性能。所以我們可以用動態(tài)規(guī)劃方法，把運(yùn)算結(jié)果存儲起來,從第0項(xiàng)推導(dǎo)至第n項(xiàng),避免重復(fù)運(yùn)算。我們可以先思考其暴力遞歸的解法,把暴力遞歸的過程抽象成狀態(tài)轉(zhuǎn)移方程,確定可變參數(shù),從基本情況(base case)開始推理,通過狀態(tài)轉(zhuǎn)移方程,得出最優(yōu)解,從而減少冗余運(yùn)算。public class Solution { public int Fibonacci(int n) { //基本情況 if (n==0){ return 0; } if (n<=1){ return 1; } int dp[]=new int[n+1]; dp[0]=0; dp[1]=1; for(int i=2;i //狀態(tài)轉(zhuǎn)移方程 dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; }}復(fù)雜度分析:??需要開辟長度為n+1的dp數(shù)組,同時(shí)遍歷整個(gè)數(shù)組，故時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。

細(xì)心的你會發(fā)現(xiàn)，根據(jù)斐波那契數(shù)列的狀態(tài)轉(zhuǎn)移方程，當(dāng)前狀態(tài)只和之前的兩個(gè)狀態(tài)有關(guān)，其實(shí)并不需要那么長的一個(gè) DP 數(shù)組來存儲所有的狀態(tài)，只要想辦法存儲之前的兩個(gè)狀態(tài)就行了。所以可以進(jìn)一步優(yōu)化，把空間復(fù)雜度降為 O(1)。

??????三、斐波那契數(shù)列通項(xiàng)公式?

對于這道題目，我們還可以通過斐波那契數(shù)列通項(xiàng)公式求解,但這個(gè)數(shù)學(xué)方法僅限于標(biāo)準(zhǔn)的斐波那契數(shù)列問題求解,無法應(yīng)對斐波那契數(shù)列的變種問題。公式如下：?public class Solution { public int Fibonacci(int n) { Long fib = Math.round((Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) / Math.sqrt(5)); return fib.intValue(); }}?復(fù)雜度分析:將n代入公式即可得到答案,其中Math.pow(a,b)為求a的b次方、Math.sqrt(a)為求a的正平方根、Math.round(a)為取a最接近的整數(shù)(可簡單理解為四舍五入取整).對于pow、sqrt、round方法,我們都可以放心地認(rèn)為其時(shí)間復(fù)雜度為O(1),因而總的時(shí)間復(fù)雜度為O(1)。我們使用變量fib存儲運(yùn)算結(jié)果,因此空間復(fù)雜度為O(1)。? ? ? ? ? ? ? ?斐波那契數(shù)列來自實(shí)現(xiàn)生活,有著諸多的變種問題,例如自然界中向日葵花蕊的排列線條順時(shí)針排列線條數(shù)為21，逆時(shí)針排列線條數(shù)為34，是兩個(gè)相鄰的斐波那契數(shù)；樹木也是以斐波那契數(shù)列的方式生長；而黃金比例也經(jīng)常被用于藝術(shù)和建筑的設(shè)計(jì)，規(guī)劃和建造許多建筑物，如教堂，寺廟，祭壇，住房以及創(chuàng)造宗教藝術(shù)品。(但其實(shí)，?斐波那契數(shù)列在“輪到你了”就真的只是個(gè)數(shù)列。)

更多精彩內(nèi)容：

(點(diǎn)擊即可閱讀)

用兩個(gè)棧實(shí)現(xiàn)隊(duì)列用隊(duì)列實(shí)現(xiàn)棧持續(xù)更新中.....后續(xù)我們還會持續(xù)更新一些有意思的算法基礎(chǔ)題目，有興趣的可以持續(xù)關(guān)注一下~ 信析團(tuán)隊(duì)持續(xù)招新，有興趣了解的小可愛可以來科技樓232詳談哦(*?▽?*)祝祖國生日快樂！?！

總結(jié)

以上是生活随笔為你收集整理的斐波那契数列c++代码_轮到你了，斐波那契数列！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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