斐波那契數列(菲波那契數列)

斐波那契數列

菲波那契數列一般指本詞條

斐波那契數列(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年起出版了以《斐波納契數列季刊》為名的一份數學雜誌,用於專門刊載這方面的研究成果。

基本介紹

  • 中文名:斐波那契數列
  • 外文名:Fibonacci sequence
  • 別稱:黃金分割數列、兔子數列
  • 表達式:F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)
  • 提出者:列昂納多·斐波那契
  • 提出時間:1202年
  • 套用學科:數學
  • 適用領域範圍:代數
  • 適用領域範圍:多個領域
  • c語言中:FIB數列
定義,通項公式,遞推公式,通項公式,通項公式推導,與黃金分割,關係,證明,特性,平方與前後項,與集合子集,奇數項求和,偶數項求和,平方求和,隔項關係,兩倍項關係,其他公式,套用,生活斐波那契,黃金分割,楊輝三角,矩形面積,質數數量,尾數循環,自然界中“巧合”,數字謎題,影視作品中的斐波那契數列,推廣,相關數學,排列組合,兔子繁殖問題,數列與矩陣,斐波那契弧線,Javascript代碼實現,C++代碼實現,python3代碼實現,

定義

斐波那契數列指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........
這個數列從第3項開始,每一項都等於前兩項之和。
自然中的斐波那契數列自然中的斐波那契數列
斐波那契數列的定義者,是義大利數學家列昂納多·斐波那契(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)
顯然這是一個線性遞推數列

通項公式

(如上,又稱為“比內公式”,是用無理數表示有理數的一個範例。)
註:此時

通項公式推導

方法一:利用特徵方程(線性代數解法)
線性遞推數列特徵方程為:
x2=x+1
解得 
.


 
解得

方法二:待定係數法構造等比數列1(初等代數解法)
設常數r,s .
使得
則r+s=1,-rs=1
n≥3時,有
……
聯立以上n-2個式子,得:
上式可化簡得:
那么
……
(這是一個以
為首項、以
為末項、
為公比的等比數列的各項的和)。
的解為
方法三:待定係數法構造等比數列2(初等代數解法)
構造方程
解得
,所以
由(1)(2)式得
化簡可得
方法四:母函式法。
對於斐波那契數列{an},有a1=a2=1,an=an-1+an-2(n>2時)
令S(x)=a1x+a2x+…+anxn+...
那么有S(x)*(1-x-x2)=a1x+(a2-a1)x2+…+(an-an-1-an-2)xn+...=x
因此S(x)=
.
不難證明1-x-x2=-(x+
)(x+
)=(1-
*x)(1-
*x).
因此S(x)=
*[x/(1-
*x)-x/(1-
*x)].
再利用展開式1/(1-x)=1+x2+…+xn+…
於是就可以得S(x)=b1x+b2x2+…+bnxn+…
其中bn=
*[(
)n - (
)n].
因此可以得到an=bn=
*[(
)- (
)]

與黃金分割

關係

有趣的是,這樣一個完全是自然數的數列,通項公式卻是用無理數來表達的。而且當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整除,
    每4個連續的數中有且只有一個被3整除,
    斐波那契數列(菲波那契數列)
    每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步的循環。

    自然界中“巧合”

    斐波那契數列在自然科學的其他分支,有許多套用。例如,樹木的生長,由於新生的枝條,往往需要一段“休息”時間,供自身生長,而後才能萌發新枝。所以,一株樹苗在一段間隔,例如一年,以後長出一條新枝;第二年新枝“休息”,老枝依舊萌發;此後,老枝與“休息”過一年的枝同時萌發,當年生的新枝則次年“休息”。這樣,一株樹木各個年份的枝椏數,便構成斐波那契數列。這個規律,就是生物學上著名的“魯德維格定律”。
    另外,觀察延齡草、野玫瑰、南美血根草、大波斯菊、金鳳花、耬斗菜、百合花、蝴蝶花的花瓣,可以發現它們花瓣數目具有斐波那契數:3、5、8、13、21、……
    其中百合花花瓣數目為3,梅花5瓣,飛燕草8瓣,萬壽菊13瓣,向日葵21或34瓣,雛菊有34,55和89三個數目的花瓣。
    斐波那契數列(菲波那契數列)
    斐波那契螺旋:具有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
    0
    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)
    0
    1
    1
    2
    3
    5
    8
    13
    21
    34
    F[1,1](n-1)
    0
    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
    0
    1
    1
    2
    3
    5
    8
    13
    21
    34
    55
    成兔對數
    0
    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))T
    F(n) =(1,0 ) (F(n),F(n-1))T
    它的運算就是右邊的矩陣 (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))T= A^(n)*(1,1)T
    這就是斐波那契數列的矩陣乘法定義。
    另矩陣乘法的一個運算法則A^n(n為偶數) = A^(n/2)* A^(n/2),這樣我們通過二分的思想,可以實現對數複雜度的矩陣相乘。
    因此可以用遞歸的方法求得答案。
    數列值的另一種求法
    F(n) = [ (( sqrt ( 5 ) + 1 ) / 2) ^ n ]
    其中[ x ]表示取距離 x 最近的整數。

    斐波那契弧線

    斐波那契弧線,也稱為斐波那契扇形線。第一,此趨勢線以二個端點為準而畫出,例如,最低點反向到最高點線上的兩個點。然後通過第二點畫出一條“無形的(看不見的)”垂直線。然後,從第一個點畫出第三條趨勢線:38.2%, 50%和61.8%的無形垂直線交叉。
    斐波那契數列(菲波那契數列)
    斐波納契弧線,是潛在的支持點和阻力點水平價格。斐波納契弧線和斐波納契扇形線常常在圖表里同時繪畫出。支持點和阻力點就是由這些線的交匯點得出。
    要注意的是弧線的交叉點和價格曲線會根據圖表數值範圍而改變,因為弧線是圓周的一部分,它的形成總是一樣的。

    Javascript代碼實現

    function* fibo(){    let [pre,curr] = [0,1];    for(;;){        yield curr;        [pre,curr] = [curr,pre + curr];    }}for(let i of fibo()){    if(i > 10000){        break;    }    console.log(i);}//實現10000以內的數列

    C++代碼實現

    基本循環算法
    # include <iostream># include <cstdio>using namespace std;int main(){        int a=0,b=1,c=1,n;        cin>>n;//輸入n        for(int i=3;i<=n;i++){                a=b;                b=c;                c=a+b;        }        cout<<c; //輸出最終結果         return 0;}
    遞歸算法實現
    # include <iostream># include <cstdio>using namespace std;int f(int n){    if(n==0) return 0;    if(n==1) return 1;    if(n>=2){        return f(n-1)+f(n-2);    }}int main(){    int n;    cin>>n;    printf("%d",f(n));    return 0;}
    遞歸算法最佳化(記憶化搜尋)
    # include <iostream># include <cstdio># define 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;    printf("%d",f(n));    return 0;}
    高精度計算
    #include<iostream>#include<cstring>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<n+1;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<<s2<<endl;    return 0;}

    python3代碼實現

    def fib(n):    a, b = 1, 1      while a < n:            print(a, end=' ')            a, b = b, a+b   fib(100) #輸出的是100以內的斐波那契數列

    相關詞條

    熱門詞條

    聯絡我們