斐波那契数列非递归C语言竟暗藏这般玄机

/*前边两个为一种做法*/

/*后边有另外的做法（差分方程以及利用矩阵去做）*/

这段内容似乎并不是一个完整的句子类型, 它看起来像是代码中的注释分隔符重复罗列, 不太明确你具体要求改写什么, 如果是要对这样的形式进行“改写式玩弄”, 可以这样: //***************************************************, //***************************************************, //***************************************************。但感觉这样意义不大, 你可以进一步明确下需求。

第一种做法

这是题目, 属于2018王道数据结构考研复习指导, 是第一章思维拓展方面的。

关于斐波那契数列的简介：

如此这般一个数列, 即0、1、1、2、3、5、8、13、21、34、……它被叫做斐波那契数列, 又被称作黄金分割数列 , 在数学范畴里, 斐波纳契数列是通过这样一种被以递归方式进行定义的: F（0）等于0, F（1）等于1, F（n）等于F(n - 1)加上F(n - 2)（n大于或等于2, n属于正整数）, 在现代物理、准晶体结构、化学等诸多领域, 斐波纳契数列均存在直接的应用, 鉴于此, 美国数学会自1963年起出版了一份名为《斐波纳契数列季刊》的数学杂志, 用以专门刊载这方面的研究成果。

具体题目：

得出斐波那契数列的F(n)存有两种常用算法为: 递归算法以及非递归算法, 去剖析两种算法的时间复杂度。

1.递归算法

1#include2usingnamespacestd;34longFibonacci(intn) {5if(n ==0)6return0;7elseif(n ==1)8return1;9else10returnFibonacci(n -1) + Fibonacci(n-2);11}1213intmain() {14cout <<"Enter an integer number:"<<endl;15intN;16cin >>N;17cout << Fibonacci(N) <<endl;18system("pause");19return0;20}

时间复杂度分析：

对于求解F(n), 要算出它, 必定得先去计算F(n - 1)以及F(n - 2) , 而计算F(n - 1)和F(n - 2) , 又一定得先计算F(n - 3)和F(n - 4) , 并且不断这样类推下去 , 一直到一定得先计算F(1)和F(0) , 之后再通过逆推得出F(n - 1)和F(n - 2)的结果 , 进而得到F(n) , 但这样会计算诸多重复的值 , 在时间方面造成了极大的浪费 , 算法的时间复杂度随同N的增大呈现指数式的增长 , 时间的复杂度为O(2^n) , 也就是2的n次方。

2.非递归算法

1#include2usingnamespacestd;34longFibonacci(intn) {5if(n <=2)6return1;7else{8longnum1 =1;9longnum2 =1;10for(inti =2;i < n -1;i++) {11num2 = num1 +num2;12num1 = num2 -num1;13}14returnnum1 +num2;15}16}1718intmain() {19cout <<"Enter an integer number:"<<endl;20intN;21cin >>N;22cout << Fibonacci(N) <<endl;23system("pause");24return0;25}

时间复杂度分析：

从大于二的n开始着手计算 , 借助F( n - 1)以及F( n - 2)这两个数进行相加以得出结果 , 如此这般便规避了大量的重复计算 , 其效率相较于递归算法要快出许多 , 算法的时间复杂度与n成正比例关系 , 也就是算法的时间复杂度为O( n )。

第二种做法。

应用网址：

斐波那契数列, f(n)等于f(n减1)加上f(n减2), n大于或等于2。

f(0)=0; f(1)=1;

即有名的兔子繁衍问题。

斐波那契数列共有三种解法，因而写这篇文章总结一下。

1. 递归求解

递归求解比较简单，是大家常见的一种解法。

1intfibonacci(intn)2{3cout<<"calculating"<endl;4if(n<=0) {5return0;6}7if(n==1) {8return1;9}10returnfb(n-1)+fb(n-2);11}

关于这种解法，不再赘述，下面主要说下时间复杂度分析。

设有一个函数f(n), 它是当参数为n的时候的时间复杂度, 存在这样一种情况，非常明显地可以看到: f(n)等于f(n减1)加上f(n减2)。

这就转化为了数学上的二阶常系数差分方程，并且为其次方程。

于是就转化成了求解f(n)的值的情况, f(n)等于f(n - 1)加上f(n - 2), 并且f(0)的取值是0, f(1)的取值是1。

特征方程为：x^2-x-1=0

得 x=(1±√5)/2

因而f(n)的通解为:

由f(0)=0; f(1)=1可解得c_1，c_2

最终可得，时间复杂度为：

第一种解法具备相对简单的特性, 然而会出现多个元素被重复进行计算的状况, 所以时间复杂度在程度方面较高, 为了达成避免重复计算这一目标, 可以通过开展循环计算的方式来降低时间复杂度。

1intFibonacci(intn) {2if(n<=0) {3return0;4}5if(n==1) {6return1;7}8intmin=0;9intmax=1;10inti=2;11intresult=0;12while(i<=n) {13result=min+max;14min=max;15max=result;16++i;17} return result; }

第二种算法时间复杂度为O(n)

3. 还有一种时间复杂度更低的算法。

根据上面的递归公式，我们可以得到

所以呢, 计算f(n)就被简化了, 简化成了计算矩阵的(n-2)次方, 然而计算矩阵的那(n-2)次方时, 我们能够进一步去做分解, 也就是计算矩阵(n-2)/2次方的平方, 而且还能一步步地持续分解下去, 鉴于采用折半的方式去计算矩阵次方, 所以时间复杂度是O(log n)。

具体代码实现如下：

1//2//main.cpp3//fibonaccimatrix4//5//Created by shunagao on 15/8/31.6//Copyright © 2015年 shunagao. All rights reserved.7//89#include10usingnamespacestd;1112classMatrix13{14public:15intn;16int**m;17Matrix(intnum)18{19m=newint*[num];20for(inti=0; i) {21m[i]=newint[num];22}23n=num;24clear();25}26voidclear()27{28for(inti=0; ii) {29for(intj=0; jj) {30m[i][j]=0;31}32}33}34voidunit()35{36clear();37for(inti=0; ii) {38m[i][i]=1;39}40}41Matrixoperator=(constMatrix mtx)42{43Matrix(mtx.n);44for(inti=0; ii) {45for(intj=0; jj) {46m[i][j]=mtx.m[i][j];47}48}49return*this;50}51Matrixoperator*(constMatrix &mtx)52{53Matrix result(mtx.n);54result.clear();55for(inti=0; ii) {56for(intj=0; jj) {57for(intk=0; kk) {58result.m[i][j]+=m[i][k]*mtx.m[k][j];59}60}61}62returnresult;63}64};65intmain(intargc,constchar*argv[]) {66unsignedintnum=2;67Matrix first(num);68first.m[0][0]=1;69first.m[0][1]=1;70first.m[1][0]=1;71first.m[1][1]=0;72intt;73cin>>t;74Matrix result(num);75result.unit();76intn=t-2;77while(n) {78if(n%2) {79result=result*first;80}81first=first*first;82n=n/2;83}84cout<<(result.m[0][0]+result.m[0][1])<<endl;85return0;86}