实用文档之斐波那契数列

1、实用文档之”斐波那契数列”简介斐波那契数列(Fibonacci),又称黄金分割数列，由数学家斐波那契最 早以“兔子繁殖问题"引入，推动了数学的发展。故斐波那契数列又称“兔子 数列“。斐波那契数列指这样的数列：1,123,5,&13,，前两个数的和等于 后面一个数字。这样我们可以得到一个递推式，记斐波那契数列的第/项 为 Ft,则 Fi=Fi+Fi-2.兔子繁殖问题指设有一对新生的兔子，从第三个月开始他们每个月都 生一对兔子，新生的兔子从第三个月开始又每个月生一对兔子。按此规律, 并假定兔子没有死亡，10个月后共有多少个兔子？这逍题目通过找规律发现答案就是斐波那契数列，第&qu

2、ot;个月兔子的数 量是斐波那契数列的第"项。性质如果要了解斐波那契数列的性质，必然要先知道它的通项公式才能更 简单的推导出一些立理。那么下面我们就通过初等代数的待泄系数法汁算 出通项公式。令常数 p,q 满足 Fn-pFn.I=q(Fn-l-pFn-2)o 则可得：Fn-pFn=q(FmrpFa=q2(Fn-2-pFn-3)=.=严疔2旳又/ Fn-pFn.t=q( Fn-t-pFn.2). Fn-pFn-1 =qFn-l-pqFn-2FH-1 + Fz-P Fn-q Fn+ pq F»2=0(l-p-q)Fn-i+(l +pq)Fn-2=0:.p+q=l,pq=-l是其

3、中的一种方程组 Fn-pFni=严(F? 一pFj=q“(_p)=旷F尸旷Lp(q”-2+p(旷 4 )尸旷 Lp"-2+p2 旷 3+ 勺戶不难看岀，上式是一个以/沟为公比的等比数列。将它用求和公式求 和可以得到：而上而出现了方程组p+q=l,pq=-l,可以得到p(l-p)=-l,p2-p-=0,这 样就得到了一个标准的一元二次方程，配方得 p2-p+0.25=1.25,(p-0.5F=1.25,p=±71.25+0.5。随意取出一组解即可:22这就是著名的斐波那契数列通项公式。有了它，斐波那契数列的一些 性质也不难得出了。比如斐波那契数列相邻两项的比值趋向于黄金分割比

4、, 即：lim1.6180339887.因为n是趋向于正无限的，因此我们可以知道:那么我们就可以把分子和分母的第二项同时省略掉，即这就是斐波那契数列的魅力之一它和黄金分割比有密切的关系。 下面将给出斐波那契数列的几个性质及其证明。1 丿 Fl +F2+Fs+ +F/i=Fn2-l证明:原式=(F3F2)+(F4-F3)十+(Fx2-Fg 1丿=&+212丿F1 +凡+尸5+F2卄1 =尸2卄2证明:原式=尸2+( FgF2)+( FxF4)+( F2卄2F2n)=F2n+23) F2+F22+. +F2=FnFn+i证明：利用数学归纳法，显然“=1时满足，下而证明若时满足， n=k+时

5、也满足.已知Fi?十 F2?十+F,=F”Fn+i,F 卩十 F?'+F时 i?=F”F”+i+Fh+F=(F时 I 十 F”)F”+i=F” 因此“+1后仍然满足上述公式成立.4）FiF2+F?Fs+FhF”“=（F卄 22FnFn+l）/2证明：数学归纳法,“1时满足已知DF2+F2F3+m+i满足，那卩旧十尸2凡+几几+1+几+1几+2=(几+2丄 Wh1 V2+几+1几+2=(Fn+22-FnFn+1 +2Fn+iFn+2- )/2=( Fn+22+2F+iFn+2+Fn+i2)- FnFn+i-Fn+M/2=(Fn+AFfl+iFn+2-lX?> 因此上式成立.5) F

6、2=F.iFn+i+(-rl证明：数学归纳法，”=2时满足已知前面的"都满足，那么Fn2=F.i2+Fn.22+2F- n-2Fn-l=F2+FnjFn+(Ar'l+2F2Fn-l=Fn-lFn+Fn-r+(-l)n'=Fn-lEr+l+M/，+1,因此上式成立.6) F”+m=Fn“Fr+FfnF1)证明：利用通项公式，设alB+厂Frn-lFn +Vn4 1=岂(尹"-严 JO” -閃)+ (am -严)(/1 - 0” 卜 1) = £(注意到 /a+a=sqrt(5)=/,/a=O=/a,上式就变成了这就是上述公式的证明.斐波那契数列与自然

7、斐波那契数列中的斐波那契数会经常出现在我们的眼前比如松 果、凤梨、树叶的排列、某些花朵的花瓣数（典型的有向日葵花瓣），蜂巢, 蜻蜓翅膀，超越数c （可以推出更多），黄金矩形、黄金分割、等角螺线， 十二平均律等。斐波那契数还可以在植物的叶、枝、茎等排列中发现。例如，在树木 的枝干上选一片叶子，记其为数0,然后依序点数叶子（假泄没有折损）， 直到到达与那些叶子正对的位置，则苴间的叶子数多半是斐波那契数。叶 子从一个位置到达下一个正对的位苣称为一个循回。叶子在一个循回中旋 转的圈数也是斐波那契数。在一个循回中叶子数与叶子旋转圈数的比称为 叶序(源自希腊词，意即叶子的排列)比。多数的叶序比呈现为斐波那

8、契 数的比。图为斐波那契弧线。关于递推式的拓展研究错位排列问题有”个数，求有多少种排列使这“个数都不在原来的位巻上。比如“=2时，有一种排列。设夬“)表示“个数的错位排列数量，分两种情况讨论：1. 第“个数在第畑n)个数的位宜上，第p个数在第"个数的位垃 上，则此时共有金-2)种选择。由于p有(”-1)种值，则总共有种排列方法；2. 否则，共有(ml如)种排列方法。综上所述，夬“)=(”1)如)伽2), .A 1 )=02)= U那这个数列的通项 公式是什么呢？直接对这个数列不好进行操作，可以转化一下。设错位排 列的概率函数为g(”)，英中g(l)=O,g(2)=O.5°在

9、知)的递推式两边同时除以 “!即可得到“仇)=如乩一 2) +吕(“- 1)。两边同时乘“得到"&(”)=(“-1 )g("-1 )+g(”-2)”(g(")-g(n-1 )=g("-2)-g(n-1)咖)-gd - 1)=畔;即可得到呦=£耳L £畔*i = 2 ' r = 0 注意到"的泰勒展开式跟它好像有点像，是因此有如下的等式:lim 9(71)=八=0.36788n-> + 8同时，我们也可以得到了函数/的通项公式为:viC-iyfM = n!g(n) = n!-这就是一些关于错位排序的性质。

10、类斐波那契数列的研究我们知道斐波那契数列递推式为血小1)土/"2),那么假如有更多项 呢？假设血)诙1)如2)4:畑3),其中./(l)h=/(3)=1 我们暂时称这个数 列为类斐波那契数列，那么它的通项公式又如何呢？令 uJkc 满足 J(n)+aj(n-1 )+Zz?-2)=c(/(7?-l )+t/(?-2)+/?/(zi-3)则得到c-a=,ac-b=.消元得c3-c2-c-l=0,利用牛顿迭代可以计 算出c= 1.83928675521416，则“=0.83928675521416 .,D.54368901269208 所以 J(n)+af(n-1 )+bJ(n-2)=cn

11、'y( 1 +a+h),记 t=+a+b9 两边同时除以 cn 构造更多的常数项：/ (n) a /(n -1) b / (n - 2) t+ _ + =C” C 严 C G(n)=型一2)=二为了方便,我们记外丿_厂贝9：9(“)+ 夕9(n - 1) +令pg满足g(心Pg("lM=Kggl)Pg(m2)q),则得到:a btP + r= -pr = (l-r)q= cc这个方程会发现没有实数解.于是我们只能使用复数了： =022815549365396. .-032963360796702.<7=0.29087615630927 +0.07807037249863

12、i 7-0.22815549365396. +032963360796702. i继续上面的递推式，则有1 )-q) o 记 T=gpgq,则:g(n)=pg(n 1 )+FJT+q=p(pg(H2)+严、T+q)+严?T+q 詁險(1 )+严砂叼+ +严田+血 +p”2gp-1=Pn因此也就可以得到/的递推式了:不 难 得 到 ，匸2.38297576790624,1=0.12876722129781.+0.10114779836709九递推式中的cpq,f,T都是常数，但除了 c以外都是复数，因此计算上 会比较困难。在附录中附上C+的程序，附复数计算的模板和使用递推式 计算类斐波那契数列的

13、程序。递推式和矩阵如果对于每个线性递推式都要先计算它的通项公式才能够快速地得到 某一项，那这个方法太过于复杂了。于是我们可以使用矩阵来加速递推。比如斐波那契数列的递推式也可以写成：因此就有如下结果:其中矩阵的幕次方可以使用快速幕算法在O(logn)的时间内解决，因此 我们就可以在O(logn)的时间内计算出斐波那契数列的第n项(排除髙精度 的时间)，且精度要比虚数和小数精确的多。附录利用通项公式汁算类斐波那契数列的代码:include <stdio h> include <stdlib h> include <algorithm> include <s

14、tring h> include <vector> include <math h> include <queue> include <set> 廿include <functional> include <time h> using namespace std;const double EPS = 1ET5;struct Complexdouble a, b; .，nim=abiComplex& operato"(const Complex& c) a = c a;b = c. b;ret

15、urn *this;Complex () a = b = 0;Complex (double tl, double t2 = 0) a = tl;b = t2;Complex operator+(const Complex& c) const return Complex (a + c a, b + c b);Complex operator- (const Complex& c) const return Complex (a 一 c a, b c b);Complex operator* (const Complex& c) const double ta = a

16、* ca - b * cb;double tb = b * ca + a * cb;return Complex(ta, tb):Complex operator/ (const Comple?:& c) const Complex t = c;t b 二b;t = (*this) * t;double div 二 c a * c a + c b * c b;t a /= div;t b /= div;return t;bool operator=(const Complex& c) const return fabs(a 一 ca) + fabs (b 一 cb) <

17、EPS;bool operator!=(const Complex& c) const return !(*this) = c):Complex operator+(double c) const return (*this)十 Complex(c): Complex operator"(doublec)constreturn(*this)-Complex(c):Complex operator*(doublec)constreturn(#this)*Complex(c):Complex operator/(doublec)constreturn(*this)/Complex

18、(c):void print () printf C%. 141f*%. 141fin a, b) ; ;Complex csqrt (const Complex& c)Complex r = Complex(1, 1), t = Complex 0: while (r != t) t = r;r = r-(r*r-c)/2/r;return r;Complex cpow(Complex c, int e) Complex res = Complex(1, 0);for (; e; e »= 1) if (e & 1) res = res * c;c = c * c;return res:int mainO double c = 2, t = 0;while (fabs (c t) > EPS) t = c;c-=