幾種求廣義斐波那契數(shù)列的Matlab實(shí)現(xiàn)方法

曹艷華+呂廣紅

[摘 要]廣義斐波那契數(shù)列具有其一般形式，求廣義斐波那契數(shù)列通項(xiàng)的Matlab語言實(shí)現(xiàn)方法有多種。各種方法在計(jì)算中具有其優(yōu)缺點(diǎn)。這個(gè)數(shù)列有著無數(shù)的研究及應(yīng)用，這是一類最神奇的、充滿著生命力的數(shù)列，其蘊(yùn)含的數(shù)學(xué)美無法用言語來表達(dá)。

[關(guān)鍵詞]廣義Fibonacci數(shù)列;Matlab實(shí)現(xiàn)

[中圖分類號] O151 [文獻(xiàn)標(biāo)識碼] A [文章編號] 2095-3437（2016）01-0096-02

一、廣義斐波那契數(shù)列

斐波那契數(shù)列（Fibonacci Sequence）最初由意大利的數(shù)學(xué)家斐波那契于1202年提出，用來描述一類有趣的兔子繁殖問題。這個(gè)數(shù)列自誕生之日起便有著無數(shù)的研究及應(yīng)用，這是一類最神奇的、充滿著生命力的數(shù)列，其蘊(yùn)含的數(shù)學(xué)美是無法用言語來表達(dá)的。一般地，廣義斐波那契數(shù)列可定義為：

F1=a，F(xiàn)2=b，F(xiàn)n=pFn-1+qFn-2（n？叟3） ? ? ? ? ? ? ? ? ? ? （1）

這里a，b，p，q是任意的常實(shí)數(shù)。推廣后的斐波那契數(shù)列的通項(xiàng)公式有下面的定理：

定理1設(shè)x1，x2為一元二次方程x2-px-q=0的兩個(gè)根，x1=，x2=，則（a）p2+4q≠0時(shí)，廣義斐波那契數(shù)列{Fn}的通項(xiàng)公式為Fn=c1x+c2x，其中

c1=，

c2=.

（b）p2+4q=0時(shí)，廣義斐波那契數(shù)列{Fn}的通項(xiàng)公式為Fn=（c1+c2n）xn，其中x=，c1=，c2=.

二、Matlab實(shí)現(xiàn)方式

在實(shí)際應(yīng)用中，很多人感覺對這個(gè)數(shù)列無從下手去編程計(jì)算，故本文將該問題的解法及程序介紹如下。

（一）遞歸實(shí)現(xiàn)

遞歸（recursion）算法即程序在運(yùn)行的過程中調(diào)用自身的編程技巧。在本文中，使用公式f[n]=p*f[n-1]+q*f[n-2]，依次遞歸計(jì)算，遞歸結(jié)束條件是f[1]=a，f[2]=b。這種算法的優(yōu)點(diǎn)是簡潔且容易理解，缺點(diǎn)是時(shí)間復(fù)雜度太大，隨著n的增大，運(yùn)算時(shí)間將會急劇增加，增加到無法容忍的地步（后面有計(jì)算時(shí)間描述），因此在很多場合中這種方法不可取。

（二）迭代實(shí)現(xiàn)

由式（1）中的遞推關(guān)系及初值條件，可得到：

F1=a，F(xiàn)2=b，F(xiàn)3=pF2+qF1，F(xiàn)4=pF3+qF2，…，F(xiàn)n=pFn-1+qFn-2，將上述式子中的兩邊相加，整理后有：

Fn=p（F2+F3+…+Fn-1）+q（F1+F2+…+Fn-2）-（F3+F4+…+Fn-1）.

若記s=F1+F2+…+Fn-1，則上式可寫為迭代過程

Fn=（p+q-1）s+（1-p）a-qFn-1+b.

若p=q=1，a=b=1，上述迭代公式可簡化為Fn=s-Fn-1+F2，此為經(jīng)典的Fibonacci數(shù)列。這種算法的優(yōu)點(diǎn)是迭代速度很快，空間存儲量不大，計(jì)算精度高，且能得到前n項(xiàng)的和。缺點(diǎn)是每次只能計(jì)算Fn。

（三）二分矩陣法

式（1）可寫為：

FnFn-1= pFn-1+qFn-2 ? ? Fn-1=p q1 0Fn-1Fn-2=p q1 0Fn-2Fn-3=p q1 0ba，

對于任意n？叟2，廣義Fibonacci數(shù)列中任何一項(xiàng)可以用矩陣算出，每次可以得到Fn和Fn-1，而n次冪是可以在logn的時(shí)間內(nèi)算出的。缺點(diǎn)是計(jì)算精度不高，n？叟50時(shí)結(jié)果開始有誤差，且算法是不穩(wěn)定的。

（四）公式實(shí)現(xiàn)

采用定理1中的公式來計(jì)算Fn，這種方法是最沒技術(shù)含量的方法。其優(yōu)點(diǎn)是可以任意計(jì)算任一項(xiàng)，所用時(shí)間少。但由于double類型的精度還不夠，所以程序算出來的結(jié)果會有誤差，而且誤差在n？叟50時(shí)逐漸變大，算法不穩(wěn)定。

（五）隊(duì)列實(shí)現(xiàn)

在本文中，隊(duì)列算法比較適合廣義斐波那契數(shù)列，時(shí)間復(fù)雜度和空間復(fù)雜度都不大。因?yàn)镕（n）=p*F（n-1）+q*F（n-2），所以F（n）只和F（n-1）和F（n-2）有關(guān)，將F（n）加入隊(duì)列后，F(xiàn)（n-2）就可以出隊(duì)列了。

（六）遞推實(shí)現(xiàn)

由遞推初始條件F[1]=a，F(xiàn)[2]=b，使用公式F[n]=p*F[n-1]+q*F[n-2]，依次遞推計(jì)算F[n]。優(yōu)點(diǎn)是簡潔和容易理解，且每次可以同時(shí)得到F[1]，F(xiàn)[2}，…，F(xiàn)[n]。

三、計(jì)算結(jié)果比較

在本節(jié)中，可通過取不同的初值條件和遞推系數(shù)，對各種算法進(jìn)行比較。

a=b=1，p=q=1時(shí)，數(shù)值結(jié)果如下：n=50時(shí)正確結(jié)果為12586269025，公式法的計(jì)算結(jié)果絕對誤差為10-5，而別的算法均無誤差。n=100時(shí)，正確的結(jié)果為354224848179261997056，矩陣法的計(jì)算結(jié)果和正確結(jié)果一致，而公式法的計(jì)算結(jié)果為354224848179263045632，此時(shí)，公式法的誤差很大，不能再繼續(xù)運(yùn)算下去。如果想繼續(xù)使用，則必須要改進(jìn)算法，提高精度，別的方法均為精確算法。

a=b=1，p=2，q=-1時(shí)所有算法的結(jié)果均正確。a=b=1，p=-2，q=-1時(shí)所有算法的結(jié)果均正確。綜上，對于不同的初值條件和遞推系數(shù)，所有的算法（除遞歸法）所用時(shí)間都很短，遠(yuǎn)遠(yuǎn)小于1秒。

對遞歸法而言，有下面的結(jié)果（時(shí)間為秒）：

當(dāng)n>35時(shí)，所用時(shí)間超過10分鐘，這種算法已不可取。

四、完整的實(shí)現(xiàn)代碼如下：

global A B P Q;d1=input（請輸入你想要的2個(gè)初值條件：）

A=d1（1）;B=d1（2）;

d2=input（請輸入你想要的2個(gè)遞推系數(shù)：）;P=d2（1）;Q=d2（2）;

d3=input（請輸入你想要的步數(shù)n：） n=d3;

%遞歸實(shí)現(xiàn)

function s=fib（n）

global A B P Q;

if n==1

s=A;

else if n==2

s=B;

else

s=P*fib（n-1）+Q*fib（n-2）;

end

end%fib（n）即為Fn

%迭代實(shí)現(xiàn)

a=P+Q-1;b=1-P;C（1）=A;C（2）=B;S=C（1）+C（2）;

for i=3：n

C（i）=a*S+b*A-Q*C（i-1）+B;S=S+C（i）;

end%C（n）即為Fn，可以得到F1，F(xiàn)2，…，F(xiàn)n

%二分矩陣法

A1=[P，O;1，0];C=[B;A];

for k=3：n

C=A1*C;

end%C（1）即為Fn，C（2）即為Fn-1

%公式法

D=P^2+4*Q;D1=sqrt（D）;

if D==0

X=P / 2;C1=（-4*B+4*A*P） /（P^2）;C2=（4*B-2*A*P） / （P^2）;C=（C1+C2*n）*X^n;

else

X1=（P+D1） / 2;X2=（P-D1） / 2;C1=（2*B-A*（P-D1）） / （2*D1）;

C2=（2*B-A*（P+D1）） / （-2*D1）;C=C1*X1^n+C2*X2^n;

end%C即為Fn

%隊(duì)列法

Fn1=A;Fn2=B;

for k=3：n

Fn=Fn1+Fn2;Fn1=Fn2;Fn2=Fn;

end%Fn即為Fn

%遞推實(shí)現(xiàn)

c（1）=A; c（2）=B;

for i=3：n

c（i）=P*c（i-1）+Q*c（i-2）;

end %c（n）即為Fn，可以得到F1，F(xiàn)2，…，F(xiàn)n

[ 參 考 文 獻(xiàn) ]

[1] 王瑾瑜.斐波那契數(shù)列的幾種解法介紹及優(yōu)缺點(diǎn)分析[J].科技創(chuàng)新導(dǎo)報(bào)，2008（30）：241-241.

[2] 孫義欣，宋大偉.斐波那契數(shù)列問題的C語言教學(xué)實(shí)施探討[J].計(jì)算機(jī)應(yīng)用教學(xué)研究，2012（8）：151-154.

[3] 曹艷華，呂廣紅.廣義Fibonacci數(shù)列通項(xiàng)公式的充要條件[J].萍鄉(xiāng)學(xué)院學(xué)報(bào)，2015（3）：1-4.

[責(zé)任編輯：王 品]