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

/*前边两个为一种做法*//*后边有另外的做法差分方程以及利用矩阵去做*/这段内容似乎并不是一个完整的句子类型, 它看起来像是代码中的注释分隔符重复罗列, 不太明确你具体要求改写什么, 如果是要对这样的形式进行“改写式玩弄”, 可以这样: //***************************************************, //***************************************************, //***************************************************。但感觉这样意义不大, 你可以进一步明确下需求。第一种做法这是题目, 属于2018王道数据结构考研复习指导, 是第一章思维拓展方面的。关于斐波那契数列的简介如此这般一个数列, 即0、1、1、2、3、5、8、13、21、34、……它被叫做斐波那契数列, 又被称作黄金分割数列 , 在数学范畴里, 斐波纳契数列是通过这样一种被以递归方式进行定义的: F0等于0, F1等于1, Fn等于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{3coutcalculatingendl;4if(n0) {5return0;6}7if(n1) {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-10得 x(1±√5)/2因而f(n)的通解为:由f(0)0; f(1)1可解得c_1c_2最终可得时间复杂度为第一种解法具备相对简单的特性, 然而会出现多个元素被重复进行计算的状况, 所以时间复杂度在程度方面较高, 为了达成避免重复计算这一目标, 可以通过开展循环计算的方式来降低时间复杂度。1intFibonacci(intn) {2if(n0) {3return0;4}5if(n1) {6return1;7}8intmin0;9intmax1;10inti2;11intresult0;12while(in) {13resultminmax;14minmax;15maxresult;16i;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{19mnewint*[num];20for(inti0; i) {21m[i]newint[num];22}23nnum;24clear();25}26voidclear()27{28for(inti0; ii) {29for(intj0; jj) {30m[i][j]0;31}32}33}34voidunit()35{36clear();37for(inti0; ii) {38m[i][i]1;39}40}41Matrixoperator(constMatrix mtx)42{43Matrix(mtx.n);44for(inti0; ii) {45for(intj0; jj) {46m[i][j]mtx.m[i][j];47}48}49return*this;50}51Matrixoperator*(constMatrix mtx)52{53Matrix result(mtx.n);54result.clear();55for(inti0; ii) {56for(intj0; jj) {57for(intk0; kk) {58result.m[i][j]m[i][k]*mtx.m[k][j];59}60}61}62returnresult;63}64};65intmain(intargc,constchar*argv[]) {66unsignedintnum2;67Matrix first(num);68first.m[0][0]1;69first.m[0][1]1;70first.m[1][0]1;71first.m[1][1]0;72intt;73cint;74Matrix result(num);75result.unit();76intnt-2;77while(n) {78if(n%2) {79resultresult*first;80}81firstfirst*first;82nn/2;83}84cout(result.m[0][0]result.m[0][1])endl;85return0;86}