斐波那契數列
斐波那契數列
斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”。
指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波納契數列以如下被以遞推的方法定義：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在現代物理、准晶體結構、化學等領域，斐波納契數列都有直接的應用。
為此，美國數學會從1963年起出版了以《斐波納契數列季刊》為名的一份數學雜誌，用於專門刊載這方面的研究成果。
斐波那契數列指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........
自然中的斐波那契數列
斐波那契數列的定義者，是義大利數學家列昂納多·斐波那契（Leonardo Fibonacci），生於公元1170年，卒於1250年，籍貫是比薩。他被人稱作“比薩的列昂納多”。1202年，他撰寫了《算盤全書》（Liber Abacci）一書。他是第一個研究了印度和阿拉伯數學理論的歐洲人。他的父親被比薩的一家商業團體聘任為外交領事，派駐地點於阿爾及利亞地區，列昂納多因此得以在一個阿拉伯老師的指導下研究數學。他還曾在埃及、敘利亞、希臘、西西里和普羅旺斯等地研究數學。
斐波那契數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
如果設F(n）為該數列的第n項（n∈N*），那麼這句話可以寫成如下形式：:F(n)=F(n-1)+F(n-2)
顯然這是一個線性遞推數列。
(如上，又稱為“比內公式”，是用無理數表示有理數的一個範例。)
註：此時
方法一：利用特徵方程（線性代數解法）
線性遞推數列的特徵方程為：
x²=x+1
解得
，
.
則
∵
∴
解得
方法二：待定係數法構造等比數列1（初等代數解法）
設常數r，s .
使得
則r+s=1，－rs=1
n≥3時，有
……
聯立以上n-2個式子，得：
∵ ，
上式可化簡得：
那麼
……
斐波那契數列
（這是一個以 為首項、以 為末項、為公比的等比數列的各項的和）。
，的解為
斐波那契數列
方法三：待定係數法構造等比數列2（初等代數解法）
設
得
構造方程
解得，所以
由(1)(2)式得
化簡可得
方法四：母函數法。
對於斐波那契數列{a}，有a=a=1,a=a+a(n>2時)
令S(x)=ax+ax+…+ax +...
那麼有S(x)*(1-x-x)=ax+(a-a)x+…+(a-a-a)x +...=x
因此S(x)= .
斐波那契數列
斐波那契數列
不難證明1-x-x=-(x+ )(x+ )=(1- *x)(1- *x).
斐波那契數列
因此S(x)= *[x/(1- *x)-x/(1- *x)].
再利用展開式1/(1-x)=1+x+x+x+…+x +…
於是就可以得S(x)=bx+bx+…+bx +…
斐波那契數列
其中b= *[( ) - ( ) ].
斐波那契數列
因此可以得到a=b= *[( )- ( )]
有趣的是，這樣一個完全是自然數的數列，通項公式卻是用無理數來表達的。而且當n趨向於無窮大時，前一項與后一項的比值越來越逼近黃金分割0.618（或者說后一項與前一項的比值小數部分越來越逼近0.618）。
1÷1=1，1÷2=0.5，2÷3=0.666...，3÷5=0.6，5÷8=0.625…………，55÷89=0.617977……………144÷233=0.618025…46368÷75025=0.6180339886…...
越到後面，這些比值越接近黃金比.
兩邊同時除以 得到：
。
若 的極限存在，設其極限為x，
則。
所以。
由於
解得
所以極限是黃金分割比。
從第二項開始，每個偶數項的平方都比前後兩項之積少1，每個奇數項的平方都比前後兩項之積多1。
如：第二項1的平方比它的前一項1和它的后一項2的積2少1，第三項2的平方比它的前一項1和它的后一項3的積3多1。
（註：奇數項和偶數項是指項數的奇偶，而並不是指數列的數字本身的奇偶，比如從數列第二項1開始數，第4項5是奇數，但它是偶數項，如果認為5是奇數項，那就誤解題意，怎麼都說不通）
證明經計算可得：[f(n)]^2-f(n-1)f(n+1)=(-1)^(n-1)
斐波那契數列的第n+2項同時也代表了集合{1,2,...,n}中所有不包含相鄰正整數的子集個數。
斐波那契數列
f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1，且n≥1]
f(2n)/f(n)=f(n-1)+f(n+1)
斐波那契數列中的斐波那契數會經常出現在我們的眼前——比如松果、鳳梨、樹葉的排列、某些花朵的花瓣數（典型的有向日葵花瓣），蜂巢，蜻蜓翅膀，超越數e（可以推出更多），黃金矩形、黃金分割、等角螺線，十二平均律等。
斐波那契數與植物花瓣3………………………
百合和蝴蝶花5……………………
藍花耬斗菜、金鳳花、飛燕草、毛茛花8………………………
翠雀花13………………………
金盞和玫瑰21……………………
紫宛34、55、89……………雛菊
斐波那契數還可以在植物的葉、枝、莖等排列中發現。例如，在樹木的枝幹上選一片葉子，記其為數0，然後依序點數葉子（假定沒有折損），直到到達與那些葉子正對的位置，則其間的葉子數多半是斐波那契數。葉子從一個位置到達下一個正對的位置稱為一個循回。葉子在一個循回中旋轉的圈數也是斐波那契數。在一個循回中葉子數與葉子旋轉圈數的比稱為葉序（源自希臘詞，意即葉子的排列）比。多數的葉序比呈現為斐波那契數的比。
隨著數列項數的增加，前一項與后一項之比越來越逼近黃金分割的數值0.6180339887..…
將楊輝三角左對齊，成如圖所示排列，將同一斜行的數加起來，即得一數列1、1、2、3、5、8、……
公式表示如下：
f⑴=C(0,0)=1。
f⑵=C(1,0)=1。
f⑶=C(2,0)+C(1,1)=1+1=2。
f⑷=C(3,0)+C(2,1)=1+2=3。
f⑸=C(4,0)+C(3,1)+C(2,2)=1+3+1=5。
f⑹=C(5,0)+C(4,1)+C(3,2)=1+4+3=8。
f⑺=C(6,0)+C(5,1)+C(4,2)+C(3,3)=1+5+6+1=13。
……
f(n)=C(n-1,0)+C(n-2,1)+…+C(n-1-m,m) (m<=n-1-m)
斐波那契數列與矩形面積的生成相關，由此可以導出一個斐波那契數列的一個性質。
斐波那契數列
斐波那契數列的整除性與質數生成性
每3個連續的數中有且只有一個被2整除，
斐波那契數列
每5個連續的數中有且只有一個被5整除，
每6個連續的數中有且只有一個被8整除，
每7個連續的數中有且只有一個被13整除，
每8個連續的數中有且只有一個被21整除，
每9個連續的數中有且只有一個被34整除，
.......
我們看到第5、7、11、13、17、23位分別是質數：5，13，89，233，1597，28657（第19位不是）
斐波那契數列的質數無限多嗎？
斐波那契數列的個位數：一個60步的循環
11235,83145,94370,77415,61785.38190,
99875,27965,16730,33695,49325,72910…
進一步，斐波那契數列的最後兩位數是一個300步的循環，最後三位數是一個1500步的循環，最後四位數是一個15000步的循環，最後五位數是一個150000步的循環。
斐波那契數列在自然科學的其他分支，有許多應用。例如，樹木的生長，由於新生的枝條，往往需要一段“休息”時間，供自身生長，而後才能萌發新枝。所以，一株樹苗在一段間隔，例如一年，以後長出一條新枝；第二年新枝“休息”，老枝依舊萌發；此後，老枝與“休息”過一年的枝同時萌發，當年生的新枝則次年“休息”。這樣，一株樹木各個年份的枝椏數，便構成斐波那契數列。這個規律，就是生物學上著名的“魯德維格定律”。
斐波那契數列
斐波那契螺旋：具有13條順時針旋轉和21條逆時針旋轉的螺旋的薊的頭部
這些植物懂得斐波那契數列嗎？應該並非如此，它們只是按照自然的規律才進化成這樣。這似乎是植物排列種子的“優化方式”，它能使所有種子具有差不多的大小卻又疏密得當，不至於在圓心處擠了太多的種子而在圓周處卻又稀稀拉拉。葉子的生長方式也是如此，對於許多植物來說，每片葉子從中軸附近生長出來，為了在生長的過程中一直都能最佳地利用空間（要考慮到葉子是一片一片逐漸地生長出來，而不是一下子同時出現的），每片葉子和前一片葉子之間的角度應該是222.5度，這個角度稱為“黃金角度”，因為它和整個圓周360度之比是黃金分割數0.618033989……的倒數，而這種生長方式就決定了斐波那契螺旋的產生。向日葵的種子排列形成的斐波那契螺旋有時能達到89，甚至144條。1992年，兩位法國科學家通過對花瓣形成過程的計算機模擬實驗，證實了在系統保持最低能量的狀態下，花朵會以斐波那契數列長出花瓣。
三角形的三邊關係定理和斐波那契數列的一個聯繫：
現有長為144cm的鐵絲，要截成n小段（n>2），每段的長度不小於1cm，如果其中任意三小段都不能拼成三角形，則n的最大值為多少？
分析：由於形成三角形的充要條件是任何兩邊之和大於第三邊，因此不構成三角形的條件就是存在兩邊之和不超過另一邊。截成的鐵絲最小為1，因此可以放2個1，第三條線段就是2（為了使得n最大，因此要使剩下來的鐵絲儘可能長，因此每一條線段總是前面的相鄰2段之和），依次為：1、1、2、3、5、8、13、21、34、55，以上各數之和為143，與144相差1，因此可以取最後一段為56，這時n達到最大為10。
我們看到，“每段的長度不小於1”這個條件起了控制全局的作用，正是這個最小數1產生了斐波那契數列，如果把1換成其他數，遞推關係保留了，但這個數列消失了。這裡，三角形的三邊關係定理和斐波那契數列發生了一個聯繫。
在這個問題中，144>143，這個143是斐波那契數列的前n項和，我們是把144超出143的部分加到最後的一個數上去，如果加到其他數上，就有3條線段可以構成三角形了。
斐波那契數列在歐美可謂是盡人皆知，於是在電影這種通俗藝術中也時常出現，比如在風靡一時的《達芬奇密碼》里它就作為一個重要的符號和情節線索出現，在《魔法玩具城》里又是在店主招聘會計時隨口問的問題。可見此數列就像黃金分割一樣流行。可是雖說叫得上名，多數人也就背過前幾個數，並沒有深入理解研究。在電視劇中也出現斐波那契數列，比如：日劇《考試之神》第五回，義嗣做全國模擬考試題中的最後一道數學題~在FOX熱播美劇《Fringe》中更是無數次引用，甚至作為全劇宣傳海報的設計元素之一。
斐波那契—盧卡斯數列
盧卡斯數列1、3、4、7、11、18…，也具有斐波那契數列同樣的性質。（我們可稱之為斐波那契—盧卡斯遞推：從第三項開始，每一項都等於前兩項之和f(n) = f(n-1)+ f(n-2)。
盧卡斯數列的通項公式為 f(n)=[(1+√5)/2]^n+[(1-√5)/2]^n
這兩個數列還有一種特殊的聯繫（如下表所示），F(n)*L(n)=F(2n)，及L(n)=F(n-1)+F(n+1)
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … |
| 斐波那契數列F(n) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | … |
| 盧卡斯數列L(n) | 1 | 3 | 4 | 7 | 11 | 18 | 29 | 47 | 76 | 123 | … |
| F(n)*L(n) | 1 | 3 | 8 | 21 | 55 | 144 | 377 | 987 | 2584 | 6765 | … |
類似的數列還有無限多個，我們稱之為斐波那契—盧卡斯數列。
如1，4，5，9，14，23…，因為1，4開頭，可記作F[1，4]，斐波那契數列就是F[1，1]，盧卡斯數列就是F[1，3]，斐波那契—盧卡斯數列就是F[a，b]。
斐波那契—盧卡斯數列之間的廣泛聯繫
①任意兩個或兩個以上斐波那契—盧卡斯數列之和或差仍然是斐波那契—盧卡斯數列。
如：F[1,4]n+F[1,3]n=F[2,7]n，F[1,4]n-F[1,3]n=F[0,1]n=F[1,1](n-1），
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … |
| F[1,4]n | 1 | 4 | 5 | 9 | 14 | 23 | 37 | 60 | 97 | 157 | … |
| F[1,3]n | 1 | 3 | 4 | 7 | 11 | 18 | 29 | 47 | 76 | 123 | … |
| F[1,4]n-F[1,3]n | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | … | |
| F[1,4]n+F[1,3]n | 2 | 7 | 9 | 16 | 25 | 41 | 66 | 107 | 173 | 280 | … |
②任何一個斐波那契—盧卡斯數列都可以由斐波那契數列的有限項之和獲得，如
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … |
| F[1,1](n) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | … |
| F[1,1](n-1) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | … | |
| F[1,1](n-1) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | … | |
| F[1,3]n | 1 | 3 | 4 | 7 | 11 | 18 | 29 | 47 | 76 | 123 | … |
黃金特徵與孿生斐波那契—盧卡斯數列
斐波那契—盧卡斯數列的另一個共同性質：中間項的平方數與前後兩項之積的差的絕對值是一個恆值，
斐波那契數列：|1*1-1*2|=|2*2-1*3|=|3*3-2*5|=|5*5-3*8|=|8*8-5*13|=…=1
盧卡斯數列：|3*3-1*4|=|4*4-3*7|=…=5
F[1，4]數列：|4*4-1*5|=11
F[2，5]數列：|5*5-2*7|=11
F[2，7]數列：|7*7-2*9|=31
斐波那契數列這個值是1最小，也就是前後項之比接近黃金比例最快，我們稱為黃金特徵，黃金特徵1的數列只有斐波那契數列，是獨生數列。盧卡斯數列的黃金特徵是5，也是獨生數列。前兩項互質的獨生數列只有斐波那契數列和盧卡斯數列這兩個數列。
而F[1，4]與F[2，5]的黃金特徵都是11，是孿生數列。F[2，7]也有孿生數列：F[3，8]。其他前兩項互質的斐波那契—盧卡斯數列都是孿生數列，稱為孿生斐波那契—盧卡斯數列。
廣義斐波那契數列
斐波那契數列的黃金特徵1，還讓我們聯想到佩爾數列：1，2，5，12，29，…，也有|2*2-1*5|=|5*5-2*12|=…=1（該類數列的這種特徵值稱為勾股特徵）。
佩爾數列Pn的遞推規則：P1=1，P2=2，Pn=P(n-2)+2P(n-1).
據此類推到所有根據前兩項導出第三項的通用規則：f(n) = f(n-1) * p + f(n-2) * q，稱為廣義斐波那契數列。
當p=1，q=1時，我們得到斐波那契—盧卡斯數列。
當p=1，q=2時，我們得到佩爾—勾股弦數（跟邊長為整數的直角三角形有關的數列集合）。
當p=2，q=-1時，我們得到等差數列。其中f1=1，f2=2時，我們得到自然數列1，2，3，4…。自然數列的特徵就是每個數的平方與前後兩數之積的差為1（等差數列的這種差值稱為自然特徵）。
具有類似黃金特徵、勾股特徵、自然特徵的廣義——斐波那契數列p=±1。
當f1=1，f2=2，p=2，q=0 時，我們得到等比數列1，2，4，8，16……
有一段樓梯有10級台階，規定每一步只能跨一級或兩級，要登上第10級台階有幾種不同的走法?
這就是一個斐波那契數列：登上第一級台階有一種登法；登上兩級台階，有兩種登法；登上三級台階，有三種登法；登上四級台階，有五種登法……
1，2，3，5，8，13……所以，登上十級，有89種走法。
類似的，一枚均勻的硬幣擲10次，問不連續出現正面的可能情形有多少種？
答案是（1/√5)*{[(1+√5)/2]^(10+2) - [(1-√5)/2]^(10+2)}=144種。
求遞推數列a⑴=1，a(n+1)=1+1/a(n）的通項公式
由數學歸納法可以得到：a(n)=F(n+1)/F(n），將斐波那契數列的通項式代入，化簡就得結果。
斐波那契數列又因數學家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數列”。
一般而言，兔子在出生兩個月後，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，那麼一年以後可以繁殖多少對兔子？
我們不妨拿新出生的一對小兔子分析一下：
第一個月小兔子沒有繁殖能力，所以還是一對
兩個月後，生下一對小兔對數共有兩對
三個月以後，老兔子又生下一對，因為小兔子還沒有繁殖能力，所以一共是三對
－－－－－－
依次類推可以列出下表：
| 經過月數 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | … |
| 幼仔對數 | 1 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | … | |
| 成兔對數 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | ||
| 總體對數 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
幼仔對數=前月成兔對數
成兔對數=前月成兔對數+前月幼仔對數
總體對數=本月成兔對數+本月幼仔對數
可以看出幼仔對數、成兔對數、總體對數都構成了一個數列。這個數列有關十分明顯的特點，那是：前面相鄰兩項之和，構成了后一項。
這個數列是義大利中世紀數學家斐波那契在<算盤全書>中提出的，這個級數的通項公式，除了具有a(n+2)=an+a(n+1)的性質外，還可以證明通項公式為：an=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}（n=1,2,3,...）
對於斐波那契數列1、1、2、3、5、8、13、……。有如下定義
F(n)=F(n-1)+F(n-2)
F(1)=1
F(2)=1
對於以下矩陣乘法
F(n+1) = (1,1 ) (F(n),F(n-1))
F(n) =(1,0 ) (F(n),F(n-1))
它的運算就是右邊的矩陣 (1,1)乘以矩陣(F(n),F(n-1))，右邊的矩陣(1,0 ) 乘以矩陣(F(n),F(n-1))，得到：
F(n+1)=F(n)+F(n-1)
F(n)=F(n)
可見該矩陣的乘法完全符合斐波那契數列的定義
設矩陣A=第一行（1，1）第二行（1，0）迭代n次可以得到：F(n+1) =A^(n) *（ F(2)，F(1)) = A^(n)*(1,1)
這就是斐波那契數列的矩陣乘法定義。
另矩陣乘法的一個運演演算法則A^n(n為偶數) = A^(n/2)* A^(n/2)，這樣我們通過二分的思想，可以實現對數複雜度的矩陣相乘。
因此可以用遞歸的方法求得答案。
數列值的另一種求法：
F(n) = [ (( sqrt ( 5 ) + 1 ) / 2) ^ n ]
其中[ x ]表示取距離 x 最近的整數。
斐波那契數列
斐波納契弧線，是潛在的支持點和阻力點水平價格。斐波納契弧線和斐波納契扇形線常常在圖表裡同時繪畫出。支持點和阻力點就是由這些線的交匯點得出。
要注意的是弧線的交叉點和價格曲線會根據圖表數值範圍而改變，因為弧線是圓周的一部分，它的形成總是一樣的。
基本循環演演算法
遞歸演演算法實現
遞歸演演算法優化(記憶化搜索)
高精度計算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | //①================================== public static long fibLoop(int num) { if(num < 1 || num > 92) return 0; long a = 1; long b = 1; long temp; for(int i = 3; i <= num; i++) { temp = a; a = b; b += temp; } return b; } //②================================== public static long fibRec(int num) { if(num < 1) return 0; if(num < 3) return 1; return fibRec(num - 1) + fibRec(num - 2); } //③================================== static long[] l = new long[93]; static { l[1] = 1; } public static long fibBuffRec(int num) { if(num < 1 || num > 92) return 0; if(l[num] == 0) l[num] = fibBuffRec(num - 1) + fibBuffRec(num - 2); return l[num]; } //④================================== static List static { list.add(BigDecimal.ZERO); list.add(BigDecimal.ONE); } public static BigDecimal fibBig(int num) { if(num < 0) return list.get(0); if (list.size() <= num) list.add(fibBig(num - 1).add(fibBig(num - 2))); return list.get(num); } |
1 2 3 4 5 | function f(n, a1 = 1, a2 = 1) { if (n <= 1) {return a1}; return f(n-1, a2, a1 + a2); } console.log(f(1450)); // 可以計算到1450位，不溢出 |
基本循環演演算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include using namespace std; int main() { int a=0,b=1,c=1,n; cin>>n;//輸入n for(int i=1;i<=n;i++) { a=b; b=c; c=a+b; } cout< return 0; } |
數組演演算法實現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include using namespace std; int main() { int a[30],i,n; cin>>n; a[1]=a[0]=1; for(i=2;i { a[i]=a[i-2]+a[i-1]; } cout< return 0; } |
遞歸演演算法實現
1 2 3 4 5 6 7 8 9 10 11 12 13 | #include using namespace std; int f(int n) { return (n<3)? 1 : f(n-1)+f(n-2);//如果是前兩項，則輸出1 } int main() { int n; cin>>n; cout< return 0; } |
遞歸演演算法優化(記憶化搜索)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | # include const int MAX=101; using namespace std; int a[MAX]; int f(int n) { if(a[n]!=-1) return a[n]; else { a[n]=f(n-1)+f(n-2); return a[n]; } } int main() { int n; cin>>n; for(int i=0;i<=MAX-1;i++) {//初始化 a[i]=-1; } a[0]=0;a[1]=1; cout< return 0; } |
高精度計算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include using namespace std; char sum[1200]; int s=0,m=0,n; int main() { cin>>n; string s1,s2; int a[1200],b[1200]; int he,i; s1="0"; s2="1"; for(m=2;m { memset(a,0,sizeof a); memset(b,0,sizeof b); a[0]=s1.length(); for(i=1;i<=a[0];i++) { a[i]=s1[a[0]-i]-'0'; } b[0]=s2.length(); for(i=1;i<=b[0];i++) { b[i]=s2[b[0]-i]-'0'; } he=(a[0]>b[0]?a[0]:b[0]); for(i=1;i<=he;i++) { a[i]+=b[i]; a[i+1]+=a[i]/10; a[i]%=10; } he++; while((a[he]==0)&&(he>1)) he--; for(i=he,s=0;i>=1;i--,s++) { sum[s]=a[i]+'0'; } s1=s2; s2=sum; } cout< return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #輸出在3000以內的斐波那契數列 一、從最大值考慮 numMax = int(input('please input a maxnumber : ')) def flibsOne(numMax): c = [] a, b = 0, 1 while a < numMax: a, b = b, a + b c.append(a) c.remove(c[-1]) print(c) 二、從位數考慮 num = int(input('please input a number : ')) def flibsTwo(num): list1 = [] for i in range(num): if i <=1: list1.append(1) else: list1.append(list1[-2] + list1[-1]) return list1 print(flibsTwo(num)) #輸出num位數列 第三種，根據f（n）= f(n-1)+f(n-2)實現 Fbs = [1,1]#斐波那契數列前兩位 n = 3 s = input("Maxmun ")#輸入最大次數 while n != （int(s)+1） :#因為差一原則所以要再加一 a = Fbs[-1] b = Fbs[-2] fb = a+b print(str(n)+" "+str(fb)) n = n +1 Fbs.append(fb) |
1 2 3 4 5 6 7 8 9 10 11 | $n = 輸入值; if ($n >= 3) { $x = 1;$y = 1;$n = $n - 2; do { $fs = $x + $y; $x = $y; $y = $fs; echo $fs.','; $n--; } while ($n > 0); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 | // Rust代碼實現 fn main() { println!("{} {} {} {} {}", fib(0), fib(1), fib(2), fib(3), fib(4)); } fn fib(d: i32) -> i32 { if d == 0 || d == 1 { d } else { ficc(d - 2) + ficc(d - 1) } } |
基本信息
- 中文名
- 斐波那契數列
- 外文名
- Fibonacci sequence
- 提出時間
- 1202年
- 別名
- 黃金分割數列、兔子數列
- 表達式
- F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)
- 提出者
- 應用學科
- 數學
- 適用領域
- 代數等多個領域
- C語言中
- FIB數列
- 適合領域範圍
- 代數