幾種求廣義斐波那契數列的Matlab實現方法

曹艷華+呂廣紅

[摘 要]廣義斐波那契數列具有其一般形式，求廣義斐波那契數列通項的Matlab語言實現方法有多種。各種方法在計算中具有其優缺點。這個數列有著無數的研究及應用，這是一類最神奇的、充滿著生命力的數列，其蘊含的數學美無法用言語來表達。

[關鍵詞]廣義Fibonacci數列;Matlab實現

[中圖分類號] O151 [文獻標識碼] A [文章編號] 2095-3437（2016）01-0096-02

一、廣義斐波那契數列

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

F1=a，F2=b，Fn=pFn-1+qFn-2（n？叟3） ? ? ? ? ? ? ? ? ? ? （1）

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

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

c1=，

c2=.

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

二、Matlab實現方式

在實際應用中，很多人感覺對這個數列無從下手去編程計算，故本文將該問題的解法及程序介紹如下。

（一）遞歸實現

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

（二）迭代實現

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

F1=a，F2=b，F3=pF2+qF1，F4=pF3+qF2，…，Fn=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，此為經典的Fibonacci數列。這種算法的優點是迭代速度很快，空間存儲量不大，計算精度高，且能得到前n項的和。缺點是每次只能計算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數列中任何一項可以用矩陣算出，每次可以得到Fn和Fn-1，而n次冪是可以在logn的時間內算出的。缺點是計算精度不高，n？叟50時結果開始有誤差，且算法是不穩定的。

（四）公式實現

采用定理1中的公式來計算Fn，這種方法是最沒技術含量的方法。其優點是可以任意計算任一項，所用時間少。但由于double類型的精度還不夠，所以程序算出來的結果會有誤差，而且誤差在n？叟50時逐漸變大，算法不穩定。

（五）隊列實現

在本文中，隊列算法比較適合廣義斐波那契數列，時間復雜度和空間復雜度都不大。因為F（n）=p*F（n-1）+q*F（n-2），所以F（n）只和F（n-1）和F（n-2）有關，將F（n）加入隊列后，F（n-2）就可以出隊列了。

（六）遞推實現

由遞推初始條件F[1]=a，F[2]=b，使用公式F[n]=p*F[n-1]+q*F[n-2]，依次遞推計算F[n]。優點是簡潔和容易理解，且每次可以同時得到F[1]，F[2}，…，F[n]。

三、計算結果比較

在本節中，可通過取不同的初值條件和遞推系數，對各種算法進行比較。

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

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

對遞歸法而言，有下面的結果（時間為秒）：

當n>35時，所用時間超過10分鐘，這種算法已不可取。

四、完整的實現代碼如下：

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

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

d2=input（請輸入你想要的2個遞推系數：）;P=d2（1）;Q=d2（2）;

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

%遞歸實現

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

%迭代實現

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，F2，…，Fn

%二分矩陣法

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

%隊列法

Fn1=A;Fn2=B;

for k=3：n

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

end%Fn即為Fn

%遞推實現

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，F2，…，Fn

[ 參 考 文 獻 ]

[1] 王瑾瑜.斐波那契數列的幾種解法介紹及優缺點分析[J].科技創新導報，2008（30）：241-241.

[2] 孫義欣，宋大偉.斐波那契數列問題的C語言教學實施探討[J].計算機應用教學研究，2012（8）：151-154.

[3] 曹艷華，呂廣紅.廣義Fibonacci數列通項公式的充要條件[J].萍鄉學院學報，2015（3）：1-4.

[責任編輯：王 品]