编程之美 2.9 斐波那契(Fibonacci)数列
斐波那契的递归表达式如下
书中提到了三中解决方法
第一种：直接运用递归的方法来进行求解package org.wrh.programbeautiful;import java.util.Scanner;public class Topic2_9 {(String[] args) {Topic2_9 t=new Topic2_9();Scanner sc=new Scanner(System.in);int n=sc.nextInt();long time1=System.currentTimeMillis();System.out.println(“fibonacci数列中的第”+n+”个数为：”+t.fibonacci(n));System.out.println(“计算s所需的时间”+(System.currentTimeMillis()-time1));}(int n){if(n<=0){return 0;}else if(n==1){return 1;}else return fibonacci(n-1)+fibonacci(n-2);}}
这种方法的时间复杂度为：O(2^n)
由于这种方法在计算中存在大量的重复计算，因此，我们可以对计算过的F(n)进行一个记录，当下次需要计算此值时，直接拿出来用就好，这样就可以减少一定的时间复杂度，这就是我们常见的用“空间来换取时间”的方法。
实现代码如下：
package org.wrh.programbeautiful;import java.util.Arrays;import java.util.Scanner;public class Topic2_9 {int[] arr;public Topic2_9(int n){arr=new int[n+1];}(String[] args) {//Topic2_9 t=new Topic2_9();Scanner sc=new Scanner(System.in);int n=sc.nextInt();Topic2_9 t=new Topic2_9(n);long time1=System.currentTimeMillis();System.out.println(“fibonacci数列中的第”+n+”个数为：”+t.fibonacci(n));System.out.println(“计算s所需的时间： “+(System.currentTimeMillis()-time1));System.out.println(Arrays.toString(t.arr));}(int n){if(arr[n]!=0){//如果数据已经被计算过了，则直接返回即可return arr[n];}else{if(n<=0){return 0;}else if(n==1){arr[n]=1;return 1;}else {arr[n]= fibonacci(n-1)+fibonacci(n-2);return arr[n];}}}}
上面注释掉的代码为没有引入“空间”来进行数据的保存的代码。
==========================================
第二种：求出通项表达式进行求解（根据信号系统的知识） 由于斐波那契的递归表达式为：F(n)=F(n-1)+F(n-2),可知其特征方程为： x^2+x=1;解得特征值为：x1=(1+sqrt(5))/2,x2=(1+sqrt(5))/2;于是可得其通解，最后根据初始值求得其参数即可求得F(n)关于n的表达式，因此，我们就可以在时间复杂度为O(1)的时间内求出F(n) 但是当n较大的时候，所花费的时间还是巨大的，因此下面简单的介绍关于一个数的n次方的求法：二分求幂/*一个数的二分求幂的思想如下：求a^n(a的n次方) 如果n是偶数(即n%2==0) 则原来的等价于(a*a)^(n/2) , 如果是奇数则 求 a^(n-1) * a （此时n-1就变成了偶数了）。所以实现代码如下*/： power_n(int a , int n){if(n==0)return 1 ;else if(n==1)return a ;else if(n%2 == 0)return power_n(a*a , n>>1) ;elsereturn a*power_n(a , n-1) ;}也可以用while实现：可以理解为将n幂级数展开了，，循环第i次就利用了第i阶幂级数的系数。long pow1_n(int a,int n){long d=1,t=a;while(n>0){if(n%2==1)d=(d*t);n>>=1;t=t*t ;}return d;}这里的2分都用到了移位操作大大加快了速度。那么对于很多次数的幂运算就可以用二分幂运算去计算了复杂度为logn。
===============================================
第三种：分治策略进行求解(书上讲解的比较清晰)
就是利用了[F(n),F(n-1)]=[F(n-1),F(n-2)]*A;其中A为一个2*2的矩阵， 这样一个表达式，而得出了 [F(n),F(n-1)]=[F(1),F(0)]*(A^(n-1))，即求F(n)转换为了求矩阵A的 次幂，因此，实现代码与上面是类似的。 这个里面涉及到二阶矩阵乘法的运算，直接利用矩阵乘法的定义还是比较好实现的。如果涉及到高阶矩阵的乘法，则就应采用分块矩阵的乘法来进行解决了，在算法导论这本书上有详细的讲解，这里不再介绍
就会犯错误，就会有无数次让自己跌倒的机会出现，
