赞
踩
斐波那契数列(Fibonacci sequence),又称黄金分割数列,其定义为:斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…这个数列从第3项开始,每一项都等于前两项之和。
下面将介绍两种计算两种计算第n个斐波那契的方法:递归法和动态规划法。
递归法的图解如下所示:从上面的路径图来看,递归调用了9次,而加法运算了4次,Fin[1]执行了3次,Fin[0]执行了两次,重复计算影响了执行性能。
递归法程序如下所示:
//递归法
public static int Fibonacci1(int n){
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
return Fibonacci1(n - 1) + Fibonacci1(n - 2);
}
动态规划法在递归法的基础上增加了记忆机制的使用,将处理过的子问题记录下来,避免重复计算,动态规划如下图所示:
由上图看出动态规划调用了7次递归,三次加法运算,每项都只计算了一次,对于n较大时建议采用消耗空间资源,节约时间资源的方法去求解。
动态规划程序如下所示:
public static int output[] = new int[1000];//finbonacci的暂存区 //动态规划法 public static int Fibonacci(int n){ int result; result = output[n]; if(result == 0){ if(n == 0){ return 0; } if(n == 1){ return 1; } return Fibonacci1(n - 1) + Fibonacci1(n - 2); } output[n] = result; return result; }
注:本篇参考吴灿铭与胡昭敏编著的《图解算法》
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。