斐波那契数列

《斐波那契数列》由会员分享，可在线阅读，更多相关《斐波那契数列（5页珍藏版）》请在装配图网上搜索。

1、斐波那契数列姓名：林秋照学号：092312113比萨的列奥纳多，又称斐波那契(LeonardoPisano,Fibonacci,LeonardoBigollo,1175年-1250年)，意大利数学家，是西方第一个研究斐波那契数的人，并将现代书写数和乘数的位值表示法系统引入欧洲，1202年，莱昂纳多斐波那契向世人介绍了斐波那契数列，是为了解决“兔子繁殖问题”提出的。斐波那契在算盘书中提出了一个有趣的兔子问题：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？我们不妨拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能

2、力，所以还是一对；两个月后，生下一对小兔总数共有两对；三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对；依次类推可以列出下表：表中数字1，1,2，3，5，8构成了一个序列。这个数列有关十分明显的特点,那是：前面相邻两项之和，构成了后一项。LrilB土北冒!響Mtb*Ks这个数列是意大利中世纪数学家斐波那契在算盘书中提出的，这个级数的通项公式，除了具有an+2=an+an+1的性质外，还可以证明通项公式为：an=1/V5(1/2+V5/2)An-(1/2-V5/2)An(n=1,2,3)(V5表示根号5)这个通项公式中虽然所有的an都是正整数，可是它们却是由一些无理数表示出

3、来的。即在较高的序列，两个连续的斐波纳契数”的序列相互分割将接近黄金比例(1.618:1或1:0.618)。例如：233/144,987/610、斐波那契数列还有两个有趣的性质1斐波那契数列中任一项的平方数都等于兔子问题跟它相邻的前后两项的乘积加1或减1;2任取相邻的四个斐波那契数，中间两数之积(内积)与两边两数之积(外积)相差1.同样我们还可以有t阶斐波那契数列，通过递推数列a(n+t)=a(n+t-1)+a(n+t-2)+.+a(n),其中a=a(2)=1，以及对于3-t=n=2,nN*)，用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数列系数就由之前的两数相加。L1,2&瓦8,

4、13,21,3456,89,144.233,377,610,987,1597,2584,4181,6765,10946,17711,28657,48369,75025,121393,196418,317811,514229.-这个数列可以用一个简单的递推式和两个初始条件来定义：当n1时，F(n)=F(n-1)+F(n-2)F(0)=0,F(1)=1在这个数列中的数字，被称为斐波那契数。2是第3个斐波那契数。这个级数与大自然植物的关系极为密切。几乎所有花朵的花瓣数都来自这个级数中的一项数字：菠萝表皮方块形鳞苞形成两组旋向相反的螺线，它们的条数必须是这个级数中紧邻的两个数字(如左旋8行，右旋13行

5、)；还有向日葵花盘倘若两组螺线条数完全相同，岂不更加严格对称？可大自然偏不！直到最近的1993年，人们才对这个古老而重要的级数给出真正满意的解释：此级数中任何相邻的两个数，次第相除，其比率都最为接近0.618034这个值，它的极限就是所谓的黄金分割数”。自从斐波那契数列提出以来，不仅在自然界发现了许多和斐波那契数列相关的例子，而且人们还利用斐波那契数列来预测商品和证券的价格；在计算机科学领域，斐波那契数列也有许多令人感兴趣的应用，在本篇中我们要找到一个求第n个斐波那契数的精确公式，然后来讨论一下计算斐波那契数列的算法。主要讨论三种方法递归、迭代、和通项公式三种方法。第一种方法：递归法实现代码：

6、#include#includeIntfib(intn)if(n1的整数：Fib(n)=(Fib(n-1)+Fib(n-2)递归定义尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：阶乘=1基本情况对所有n1的整数：阶乘(n)=(n*阶乘(n-1)递归定义一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这是你已经知道该怎么做的。如此的定义在数学

7、中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。递归应用递归算法一般用于解决三类问题：(1) 数据的定义是按递归定义的。(Fibonacci函数)问题解法按递归算法实现。(回溯)数据的结构形式是按递归定义的。(树的遍历，图的搜索)递归的缺点：递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。这种方法的优点是简洁和容易理解，缺点是时间复杂度太大，随着n的增大，运算时间将会急剧增加。因此在很多场合这种方法是不可取的。第二种方法：迭代法实现代码：#includeint

8、f(intn);intmain()intn;scanf(%d,&n);f(n);intf(intn)inti,f1=1,f2=1,f3;if(n=0)printf(输入错误.n);elseif(n=1|n=2)printf(1);elsefor(i=0;in-2;i+)f3=f1+f2;f1表示当前的值f2=f1;f仁f3;printf(%dn,f1);利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值

9、的公式(或关系)。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。第三种方法：通项公式这种方法是最没技术含量的方法，只要你知道通项公式照着把它翻译成编程语言就可以了，优点不言而喻。fib(n)=pow(1+sqrt(5)/

10、2.0),n)/sqrt(5)-pow(1-sqrt(5)/2.0),n)/sqrt(5);这三种方法各有优缺点，使用哪种方法根据实际情况确定。从时间复杂度上来说0(通向公式法)O(迭代法)O(递归法)。由于水平有限，在百度后找到了另外的方法：矩阵法：voidmultiply(intc22,inta22,intb22,intmod)inttmp4;tmp0=a00*b00+a01*b10;tmp1=a00*b01+a01*b11;tmp2=a10*b00+a11*b10;tmp3=a10*b01+a11*b11;c00=tmp0%mod;c01=tmp1%mod;c10=tmp2%mod;c1

11、1=tmp3%mod;/计算矩阵乘法，c=a*bintfibonacci(intn,intmod)/mod表示数字太大时需要模的数if(n=0)return0;elseif(n0)if(n%2=1)multiply(result,result,a,mod);multiply(a,a,a,mod);n/=2;/二分法求矩阵幕s=(result00+result01)%mod;结果returns;intfib3(intindex)/借用vector实现if(index1)return-1;vectora(2,1);/创建一个含有2个元素都为1的向量a.reserve(3);for(inti=2;iindex;i+)a.insert(a.begin(),a.at(0)+a.at(1);a.pop_back();returna.at(0);intfib4(intindex)/队列实现if(index1)return-1;queueq;q.push(1);q.push(1);for(inti=2;iindex;i+)q.push(q.front()+q.back();q.pop();returnq.back();