裴波那契數(shù)列

1、“斐波那契數(shù)列”的發(fā)明者，是意大利數(shù)學(xué)家列昂納多斐波那契（Leonardo Fibonacci，生于公元1170年，卒于1240年，籍貫大概是比薩）。他被人稱作“比薩的列昂納多”。1202年，他撰寫了珠算原理(Liber Abaci)一書。他是第一個(gè)研究了印度和阿拉伯?dāng)?shù)學(xué)理論的歐洲人。他的父親被比薩的一家商業(yè)團(tuán)體聘任為外交領(lǐng)事，派駐地點(diǎn)相當(dāng)于今日的阿爾及利亞地區(qū)，列昂納多因此得以在一個(gè)阿拉伯老師的指導(dǎo)下研究數(shù)學(xué)。他還曾在埃及、敘利亞、希臘、西西里和普羅旺斯研究數(shù)學(xué)。斐波那契數(shù)列指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、這個(gè)數(shù)列從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。它的通項(xiàng)公式為：

2、(1/5)*(1+5)/2n - (1-5)/2n（又叫“比內(nèi)公式”，是用無理數(shù)表示有理數(shù)的一個(gè)范例。）有趣的是：這樣一個(gè)完全是自然數(shù)的數(shù)列，通項(xiàng)公式居然是用無理數(shù)來表達(dá)的?！酒婷畹膶傩浴侩S著數(shù)列項(xiàng)數(shù)的增加，前一項(xiàng)與后一項(xiàng)之比越來越逼近黃金分割的數(shù)值0.6180339887從第二項(xiàng)開始，每個(gè)奇數(shù)項(xiàng)的平方都比前后兩項(xiàng)之積多1，每個(gè)偶數(shù)項(xiàng)的平方都比前后兩項(xiàng)之積少1。（注：奇數(shù)項(xiàng)和偶數(shù)項(xiàng)是指項(xiàng)數(shù)的奇偶，而并不是指數(shù)列的數(shù)字本身的奇偶，比如第五項(xiàng)的平方比前后兩項(xiàng)之積多1，第四項(xiàng)的平方比前后兩項(xiàng)之積少1）如果你看到有這樣一個(gè)題目：某人把一個(gè)8*8的方格切成四塊，拼成一個(gè)5*13的長(zhǎng)方形，故作驚訝地問你：

3、為什么6465？其實(shí)就是利用了斐波那契數(shù)列的這個(gè)性質(zhì)：5、8、13正是數(shù)列中相鄰的三項(xiàng)，事實(shí)上前后兩塊的面積確實(shí)差1，只不過后面那個(gè)圖中有一條細(xì)長(zhǎng)的狹縫，一般人不容易注意到。斐波那契數(shù)列的第n項(xiàng)同時(shí)也代表了集合1,2,.,n中所有不包含相鄰正整數(shù)的子集個(gè)數(shù)。斐波那契數(shù)列（f(n)，f(0)=0，f(1)=1，f(2)=1，f(3)=2）的其他性質(zhì)：1.f(0)+f(1)+f(2)+f(n)=f(n+2)-12.f(1)+f(3)+f(5)+f(2n-1)=f(2n)-13.f(0)+f(2)+f(4)+f(2n)=f(2n+1)-14.f(0)2+f(1)2+f(n)2=f(n)f(n+1)5

4、.f(0)-f(1)+f(2)-+(-1)nf(n)=(-1)nf(n+1)-f(n)+16.f(m+n)=f(m-1)f(n-1)+f(m)f(n)利用這一點(diǎn)，可以用程序編出時(shí)間復(fù)雜度僅為O（log n）的程序。7.f(n)2=(-1)(n-1)+f(n-1)f(n+1)8.f(2n-1)=f(n)2-f(n-2)29.3f(n)=f(n+2)+f(n-2)10.f(2n-2m-2)f(2n)+f(2n+2)=f(2m+2)+f(4n-2m) nm-1,且n1斐波那契數(shù)列在楊輝三角中隱藏著斐波那契數(shù)列11 11 2 11 3 3 11 4 6 4 1過第一行的“1”向左下方做45度斜線，之后

5、做直線的平行線，將每條直線所過的數(shù)加起來，即得一數(shù)列1、1、2、3、5、8、斐波那契數(shù)與植物花瓣3百合和蝴蝶花5藍(lán)花耬斗菜、金鳳花、飛燕草8翠雀花13金盞草21紫宛34、55、89雛菊斐波那契數(shù)還可以在植物的葉、枝、莖等排列中發(fā)現(xiàn)。例如，在樹木的枝干上選一片葉子，記其為數(shù)0，然后依序點(diǎn)數(shù)葉子（假定沒有折損），直到到達(dá)與那息葉子正對(duì)的位置，則其間的葉子數(shù)多半是斐波那契數(shù)。葉子從一個(gè)位置到達(dá)下一個(gè)正對(duì)的位置稱為一個(gè)循回。葉子在一個(gè)循回中旋轉(zhuǎn)的圈數(shù)也是斐波那契數(shù)。在一個(gè)循回中葉子數(shù)與葉子旋轉(zhuǎn)圈數(shù)的比稱為葉序（源自希臘詞，意即葉子的排列）比。多數(shù)的葉序比呈現(xiàn)為斐波那契數(shù)的比?！鞠嚓P(guān)的數(shù)學(xué)問題】1.排列

6、組合有一段樓梯有10級(jí)臺(tái)階,規(guī)定每一步只能跨一級(jí)或兩級(jí),要登上第10級(jí)臺(tái)階有幾種不同的走法?這就是一個(gè)斐波那契數(shù)列：登上第一級(jí)臺(tái)階有一種登法；登上兩級(jí)臺(tái)階，有兩種登法；登上三級(jí)臺(tái)階，有三種登法；登上四級(jí)臺(tái)階，有五種登法1，2，3，5，8，13所以，登上十級(jí)，有89種走法。2.數(shù)列中相鄰兩項(xiàng)的前項(xiàng)比后項(xiàng)的極限當(dāng)n趨于無窮大時(shí)，F(xiàn)(n)/F(n+1)的極限是多少？這個(gè)可由它的通項(xiàng)公式直接得到，極限是(-1+5)/2，這個(gè)就是黃金分割的數(shù)值，也是代表大自然的和諧的一個(gè)數(shù)字。3.求遞推數(shù)列a(1)=1，a(n+1)=1+1/a(n)的通項(xiàng)公式由數(shù)學(xué)歸納法可以得到：a(n)=F(n+1)/F(n)，將斐

7、波那契數(shù)列的通項(xiàng)式代入，化簡(jiǎn)就得結(jié)果?！眷巢瞧鯏?shù)列別名】斐波那契數(shù)列又因數(shù)學(xué)家列昂納多斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。一般而言，兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來。如果所有兔都不死，那么一年以后可以繁殖多少對(duì)兔子？我們不妨拿新出生的一對(duì)小兔子分析一下：第一個(gè)月小兔子沒有繁殖能力，所以還是一對(duì)；兩個(gè)月后，生下一對(duì)小兔民數(shù)共有兩對(duì)；三個(gè)月以后，老兔子又生下一對(duì)，因?yàn)樾⊥米舆€沒有繁殖能力，所以一共是三對(duì)；依次類推可以列出下表：經(jīng)過月數(shù)：-1-2-3-4-5-6-7-8-9-10-11-12兔子對(duì)數(shù)：-1-1-2-3-5-8-13-21-34-5

8、5-89-144表中數(shù)字1，1，2，3，5，8構(gòu)成了一個(gè)數(shù)列。這個(gè)數(shù)列有關(guān)十分明顯的特點(diǎn)，那是：前面相鄰兩項(xiàng)之和，構(gòu)成了后一項(xiàng)。這個(gè)特點(diǎn)的證明：每月的大兔子數(shù)為上月的兔子數(shù)，每月的小兔子數(shù)為上月的大兔子數(shù)，即上上月的兔子數(shù)，相加。這個(gè)數(shù)列是意大利中世紀(jì)數(shù)學(xué)家斐波那契在算盤全書中提出的，這個(gè)級(jí)數(shù)的通項(xiàng)公式，除了具有a(n+2)=an+a(n+1)的性質(zhì)外，還可以證明通項(xiàng)公式為：an=1/（15/2）n-（1-5/2） n（n=1,2,3.） 數(shù)列定義：斐波那契數(shù)列指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、這個(gè)數(shù)列從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。它的通項(xiàng)公式為：(1/5)*(1+5)/2n - (1-5)/2n（又叫“比內(nèi)公式”，是用無理數(shù)表示有理數(shù)的一個(gè)范例。）數(shù)列屬性：1. 隨著數(shù)列項(xiàng)數(shù)的增加，前一項(xiàng)與后一項(xiàng)之比越來越逼近黃金分割的數(shù)值0.61803398872.從第二項(xiàng)開始，每個(gè)奇數(shù)項(xiàng)的平方都比前后兩項(xiàng)之積多1，每個(gè)偶數(shù)項(xiàng)的平方都比前后兩項(xiàng)之積少1。3.斐波那契數(shù)列（f(n)，f(0)=0，f(1)=1，f(2)=1，f(3)=2）的其他性質(zhì)：1.f(0)+f(1)+f(2)+f(n)=f(n+2)-12.f(1)+f(3)+f(5)+f(2n-1)=f(2n)-