几种求广义斐波那契数列的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.
[责任编辑：王 品]
[摘 要]广义斐波那契数列具有其一般形式，求广义斐波那契数列通项的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.
[责任编辑：王 品]
