本文主要是介绍Fibonacci求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
想想刚刚学C语言的时候，一开始接触递归的时候，感觉这东西实在是太不可思议了，可以将程序变得异常简洁并且非常易于理解。然后啥问题都想问递归上去扯，搞出个递归公式出来，问题就基本解决了
但是随着学习的深入，渐渐也道听途说到递归也不是那么好，因为对函数的递归调用会造成巨大的开销而且程序的运行速度也会受到限制。最近也上了些数据结构，发现书上给出递归算法的同时也会给出非递归算法！瞬间感觉，非递归好像更牛逼的样子！(关于数据结构的博文接下来也会有的，应该会结合和算法导论的阅读，我会努力写出各种非递归算法的)其实，在运用递归算法的时候，你并不一定对整个结构有完美的把握，而非递归需要你对每个细节有更完美的把握，这不论对程序的理解还是编码能力都是巨大的提高。
不知不觉居然扯了这么多
其实我是来说说Fibonacci的快速求解的，结合了书上写的，已经在看书上的解法前自己写的一些程序（居然完全不一样！）。首先是把递归求解改为非递归啦，这个应该不代码，直接上代码也就不解释什么了。
unsigned long FIB_IT(unsigned long n)
{unsigned long f_1=1,f_2=1,i,temp;if(n==1||n==2)return 1;for(i=0;i<n-2;i++){temp=f_2;f_2=f_1+f_2;f_1=temp;}return f_2;
}不过书上给出了一个用矩阵求解Fibonacci的方法，直接将O(n)的复杂度变为了O(lgn)。不过当初线代完全是靠考前刷题才拿的高分，考完就忘了，要是我估计一辈子也想不出这个方法的。其实思路也是挺简单的，附张图好了
只要知道矩阵的乘法就知道这个式子其实和Fibonacci的递推公式是一样的。因此一直推下去，就可以得到(Fn,Fn-1)
而那个n-2次方的矩阵，我们完全可以用上篇博文里的数值自乘的递归方法求解，而这也是这个程序速度更快的关键啦！下面还是结合代码来分析吧
unsigned long FIB_IT(unsigned long n)
{unsigned long aa,bb,cc,dd;if(n==1||n==2)return 1;Matrix(1UL,1UL,1UL,0UL,n-2,&aa,&bb,&cc,&dd);return aa+bb;
}void Matrix(unsigned long a,unsigned long b,unsigned long c,unsigned long d,\int n,unsigned long *aa,unsigned long *bb,unsigned long *cc,\unsigned long *dd)
{unsigned long a1,b1,c1,d1,ta,tb,tc,td;if(n==1){*aa=a,*bb=b,*cc=c,*dd=d;return;}Matrix(a,b,c,d,n>>1,&a1,&b1,&c1,&d1);*aa=ta=a1*a1+b1*c1;*bb=tb=a1*b1+b1*d1;*cc=tc=a1*c1+d1*c1;*dd=td=b1*c1+d1*d1;if(n&0x01) {//*aa=a*(*aa)+b*(*cc);//*bb=a*(*bb)+b*(*dd);//*cc=c*(*aa)+d*(*cc);//*dd=c*(*bb)+d*(*dd);*aa=a*ta+b*tc;*bb=a*tb+b*td;*cc=c*ta+d*tc;*dd=c*tb+d*td;}
}关键是那个递归函数Matrix，递归的边界值是n==1，那个时候只要将n-2次的那个矩阵返回就可以了。有一点要注意的是，当n为偶数的时候，恰好能分为两个一样的子矩阵，此时只要将子递归函数返回的矩阵自乘即可。不过如果n为奇数的话，因为子递归函数的参数是n/2，将其递归返回的子矩阵相乘在次数上与n还差1，所以还要在已求得的子矩阵乘积的基础上再乘一个(1,1,1,0)这个矩阵。在此时我就反了个非常非常低级的错误，代码就是被注释掉的那部分，竟然忘了赋值运算后值就变了= =差点debug到崩溃。
最后经过递归后，第一个Matrix返回的就是(1,1,1,0)的n-2次的矩阵啦，而Fn=a+b，Fn-1=c+d，看那个矩阵运算的式子就知道了。
为了检验它的速度我还真测试了一下，我求第1000个Fibonacci数100000次，用两种方法，出结果的速度真的是差很多的。也算再次感觉到了优秀算法的巨大魅力了吧
这篇关于Fibonacci求解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
