寧波四眼契小學(xué)英語(yǔ)

斐波那契數(shù)列（Fibonacci sequence），也稱之為黃金分割數(shù)列，由意大利數(shù)學(xué)家列昂納多?斐波那契（Leonardo Fibonacci）提出。斐波那契數(shù)列指的是這樣的一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……，這個(gè)數(shù)列從第 3 項(xiàng)開始，每一項(xiàng)都等于前面兩項(xiàng)之和。在數(shù)學(xué)上，斐波那契數(shù)列可以被遞推的方法定義如下：

F(1)=1，F(xiàn)(2)=1,?F(n)=F(n - 1)+F(n - 2)（n?≥ 3，n?∈ N*）

斐波那契數(shù)列是數(shù)學(xué)上面一個(gè)經(jīng)典的例子，并且在日常生活中有很多應(yīng)用，他還與黃金分割有著密不可分的聯(lián)系，而且當(dāng) n 趨向于無(wú)窮大時(shí)，前一項(xiàng)與后一項(xiàng)的比值越來(lái)越逼近黃金分割值 0.618。

1. 用遞歸方法求解斐指歷波那契數(shù)列

在本篇文章中，我們就需要利用遞歸的思想去求解斐波那契數(shù)列，當(dāng)給出一個(gè)斐波那契中第幾項(xiàng)的數(shù)字，然后求解出對(duì)應(yīng)的斐波那契數(shù)值。在之前，我們已經(jīng)定義了遞歸算法的相關(guān)概念，并且明確了需要應(yīng)用遞歸時(shí)候的三要素：

遞歸終止條件；

遞歸終止時(shí)候的處理方法；

遞歸中重復(fù)的邏輯提取，縮小問(wèn)題規(guī)模。

接下來(lái)，我們將利用遞歸的知識(shí)來(lái)解決斐波那契數(shù)列問(wèn)題，明確在斐波那契數(shù)列求解問(wèn)題中的遞歸三要素分別是什么。

斐波那契數(shù)列的遞歸終止條件
顯然易見，通過(guò)觀察斐波那契數(shù)列的定義，我們很容易發(fā)現(xiàn)當(dāng) n=1 或者 n=2 時(shí)，是斐波那契數(shù)列的陸前遞歸終止條件，這個(gè)時(shí)候可以給出斐波那契數(shù)列的具體值。

斐波那契數(shù)列遞歸終止時(shí)候的處理方法
同樣的，基于斐波那契數(shù)列的遞推定義唯悉搜，當(dāng)斐波那契數(shù)列達(dá)到終止條件 n=1 或者 n=2 時(shí)，我們也很容易發(fā)現(xiàn)對(duì)應(yīng)?F(1)=1，F(xiàn)(2)=1，這就是斐波那契數(shù)列在遞歸終止時(shí)對(duì)應(yīng)的取值。

斐波那契數(shù)列的遞歸重復(fù)邏輯提取
按照斐波那契數(shù)列的數(shù)學(xué)定義，F(xiàn)(n)=F(n - 1)+F(n - 2)（n?≥ 3，n?∈ N*），即當(dāng)?n?≥ 3 時(shí)，斐波那契數(shù)列中這一項(xiàng)的值等于前面兩項(xiàng)的值之和，這樣便可以將求解一個(gè)比較大的斐波那契數(shù)列轉(zhuǎn)化為求解較小數(shù)值的斐波那契數(shù)列值，這里面有重復(fù)邏輯可以遞歸復(fù)用。

例如，當(dāng)我們求解斐波那契數(shù)列中的?F(5) 時(shí)，按照定義，我們有：

F(5) =?F(4) +?F(3) // 遞歸分解
= (?F(3) +?F(2) ) + (?F(2）+F(1) ) // 遞歸求解
= [ (?F(2)+F(1) ) + 1 ] + ( 1+1 ) // 遞歸求解，遇到終止條件就求解
= [(1+1) +1 ]+(1+1) // 歸并
= 3 + 2 // 歸并
= 5 // 歸并

是的，斐波那契數(shù)列是一個(gè)集合。集合是指具有某種特定性質(zhì)的具體的或抽象的對(duì)象匯總成的集體，這些對(duì)象稱為該集合的元素。

“斐波那契”讀作：fēi?bō?nà?qì

1、斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為陵仿例子而引入，故又稱為“兔子數(shù)列”。

指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞推的方法定義：F(1)=1，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，哪鏈n∈N*）。

2、Prufer數(shù)列是無(wú)根樹的一種數(shù)列。在組合數(shù)學(xué)中，Prufer數(shù)列由有一個(gè)對(duì)于頂點(diǎn)標(biāo)過(guò)號(hào)的樹轉(zhuǎn)化來(lái)的數(shù)列，點(diǎn)數(shù)為n的樹轉(zhuǎn)化來(lái)的Prufer數(shù)列長(zhǎng)度為n-2。它可以通過(guò)簡(jiǎn)單的李汪孫迭代方法計(jì)算出來(lái)。它由Heinz Prufer于1918年在證明cayley定理時(shí)首次提出。

3、等差數(shù)列是常見數(shù)列的一種，如果一個(gè)數(shù)列從第二項(xiàng)起，每一項(xiàng)與它的前一項(xiàng)的差等于同一個(gè)常數(shù)，這個(gè)數(shù)列就叫做等差數(shù)列，而這個(gè)常數(shù)叫做等差數(shù)列的公差，公差常用字母d表示。

4、等比數(shù)列是指從第二項(xiàng)起，每一項(xiàng)與它的前一項(xiàng)的比值等于同一個(gè)常數(shù)的一種數(shù)列，常用G、P表示。這個(gè)常數(shù)叫做等比數(shù)列的公比，公比通常用字母q表示(q≠0)，等比數(shù)列a1≠ 0。其中{an}中的每一項(xiàng)均不為0。注：q=1 時(shí)，an為常數(shù)列。

5、帕多瓦數(shù)列是由帕多瓦總結(jié)而出的。它的特點(diǎn)為從第四項(xiàng)開始，每一項(xiàng)都是前面2項(xiàng)與前面3項(xiàng)的和。帕多瓦數(shù)列是：1，1，1，2，2，3，4，5，7，9，12，16，21，28，37，49，65，86，114，151……