斐波那契数列

斐波那契数列姓名：林秋照学号：092312113比萨的列奥纳多，又称斐波那契(LeonardoPisano,Fibonacci,LeonardoBigollo,1175年-1250年)，意大利数学家，是西方第一个研究斐波那契数的人，并将现代书写数和乘数的位值表示法系统引入欧洲，1202年，莱昂纳多斐波那契向世人介绍了斐波那契数列，是为了解决“兔子繁殖问题”提出的。斐波那契在算盘书中提出了一个有趣的兔子问题：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？我们不妨拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔总数共有两对；三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对；依次类推可以列出下表：表中数字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都是正整数，可是它们却是由一些无理数表示出来的。即在较高的序列，两个连续的斐波纳契数”的序列相互分割将接近黄金比例(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<=0，有a(n)=0.给出了t阶斐波那契数列的通项公式：rA(n-1)(r-1)/(t+1)r-2t)，其中r是方程xAt+1-2xAt+1=0的唯一一个大于1的正数根(可以看出r非常接近2)斐波那契数列(意大利语：SuccessionediFibonacci),又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0,F1=1,Fn=Fn-1+Fn-2(n>=2,nN*)，用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数列系数就由之前的两数相加。L1,2&瓦8,13,21,34>56,89,144.233,377,610,987,1597,2584,4181,6765,10946,17711,28657,48369,75025,121393,196418,317811,514229.-这个数列可以用一个简单的递推式和两个初始条件来定义：当n>1时，F(n)=F(n-1)+F(n-2)F(0)=0,F(1)=1在这个数列中的数字，被称为斐波那契数。2是第3个斐波那契数。这个级数与大自然植物的关系极为密切。几乎所有花朵的花瓣数都来自这个级数中的一项数字：菠萝表皮方块形鳞苞形成两组旋向相反的螺线，它们的条数必须是这个级数中紧邻的两个数字(如左旋8行，右旋13行)；还有向日葵花盘倘若两组螺线条数完全相同，岂不更加严格对称？可大自然偏不！直到最近的1993年，人们才对这个古老而重要的级数给出真正满意的解释：此级数中任何相邻的两个数，次第相除，其比率都最为接近0.618034这个值，它的极限就是所谓的"黄金分割数”。自从斐波那契数列提出以来，不仅在自然界发现了许多和斐波那契数列相关的例子，而且人们还利用斐波那契数列来预测商品和证券的价格；在计算机科学领域，斐波那契数列也有许多令人感兴趣的应用，在本篇中我们要找到一个求第n个斐波那契数的精确公式，然后来讨论一下计算斐波那契数列的算法。主要讨论三种方法递归、迭代、和通项公式三种方法。第一种方法：递归法实现代码：#include<stdio.h>#include<stdlib.h>Intfib(intn)if(n<=1)returnn;elsereturnfib(n-1)+fib(n-2);概述递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念，递归的方法是程序设计中有效的方法，采用递归编写程序能使程序变得简洁和清晰定义：它通常把一个大递归策略只需少量的递归的能力递归前进段和一般定义：程序调用自身的编程技巧称为递归(recursion)。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。意:(1) 递归就是在过程或函数里调用自身；在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。其它定义：递归的另一种定义：递归，就是用自己的简单情况，定义自己，即自己调用自己。在数学和计算机科学中，递归指由一种(或多种)简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。例如，下列为某人祖先的递归定义：某人的双亲是他的祖先(基本情况)。某人祖先的双亲同样是某人的祖先(递归步骤)。斐波那契数列是典型的递归案例：Fib(O)=0基本情况Fib(1)=1基本情况对所有n>1的整数：Fib(n)=(Fib(n-1)+Fib(n-2)递归定义尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：阶乘=1基本情况对所有n>1的整数：阶乘(n)=(n*阶乘(n-1)递归定义一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这是你已经知道该怎么做的。如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。递归应用递归算法一般用于解决三类问题：(1) 数据的定义是按递归定义的。(Fibonacci函数)问题解法按递归算法实现。(回溯)数据的结构形式是按递归定义的。(树的遍历，图的搜索)递归的缺点：递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。这种方法的优点是简洁和容易理解，缺点是时间复杂度太大，随着n的增大，运算时间将会急剧增加。因此在很多场合这种方法是不可取的。第二种方法：迭代法实现代码：#include<stdio.h>intf(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;i<n-2;i+)f3=f1+f2;f1表示当前的值f2=f1;f仁f3;printf("%dn",f1);利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。第三种方法：通项公式这种方法是最没技术含量的方法，只要你知道通项公式照着把它翻译成编程语言就可以了，优点不言而喻。fib(n)=pow(1+sqrt(5)/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;c11=tmp3%mod;/计算矩阵乘法，c=a*bintfibonacci(intn,intmod)/mod表示数字太大时需要模的数if(n=0)return0;elseif(n<=2)return1;/这里表示第0项为0,第1,2项为1inta22=1,1,1,0;intresult22=1,0,0,1;初始化为单位矩阵ints;n_=2;while(n>0)if(n%2=1)multiply(result,result,a,mod);multiply(a,a,a,mod);n/=2;/二分法求矩阵幕s=(result00+result01)%mod;结果returns;intfib3(intindex)/借用vector<int>实现if(index<1)return-1;vector<int>a(2,1);/创建一个含有2个元素都为1的向量a.reserve(3);for(inti=2;i<index;i+)a.insert(a.begin(),a.at(0)+a.at(1);a.pop_back();returna.at(0);intfib4(intindex)/队列实现if(index<1)return-1;queue<int>q;q.push(1);q.push(1);for(inti=2;i<index;i+)q.push(q.front()+q.back();q.pop();returnq.back();