php求斐波那契数的两种实现方式【递归与递推】
这篇文章主要介绍了php求斐波那契数的两种实现方式,结合实例形式分析了php使用递归与递推算法实现求斐波那契数的相关操作技巧与注意事项,需要的朋友可以参考下本文实例讲述了php求斐波那契数的两种实现方式。分享给大家供大家参考，具体如下：
斐波那契数，亦称之为斐波那契数列（意大利语： Successione di Fibonacci)，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*），用文字来说，就是斐波那契数列列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。
1 使用递归方法。顺着思路去想， f(1)= 1; f(2) = 1 ; f(3) = f(2)+f(1)【2】f(4) = f(3)+f(2) 3
//使用递归方式求斐波那契数
public function fb($n){ //
if( $n <=2){
return 1;
}else{
return fb($n-1) + fb($n-2);
}
}
2使用递推方法。
public function fb2($n){ //
if( $n <=2){
return 1;
}
$t1 = 1;$t2 = 1;
for($i=3;$i<$n;$i++){
$temp = $t1;
$t1 = $t2;
$t2 = $temp + $t2;
}
return $t1 + $t2;
}
最后，进行性能分析。
明显的可以预测，递归方法，每多一层，就要向下递归两次。 约为 O(2 的N次方)而递推算法为O(n),实测代码如下。
/**性能测试。*/
function bench_profile($starttime , $flag = ''){
$endtime = explode(' ',microtime());
$thistime = $endtime+$endtime-($starttime+$starttime);
$thistime = round($thistime,3);
return $flag."-bench:".$thistime." sec";
}
//使用递归算法。
ini_set("max_execution_time" ,3600);
$s = explode(' ',microtime());
echobench_profile($s )."<br/>";
echo fb(35); //使用递归 耗时 40.925 sec每往上一个数约慢两倍
echo bench_profile($s )."<br/>";
//使用递推算法。
$s = explode(' ',microtime());
echobench_profile($s )."<br/>";
echo fb2(35); //使用递推 时间极短。
echo bench_profile($s )."<br/>";
总结：使用递归算法，到求第100 个斐波那契数 时会卡到机器跑不动，而使用递推算法，几乎不费时间。
算法复杂度是非常重要的概念，也是区分程序员的一把好尺子。
希望本文所述对大家PHP程序设计有所帮助。
原文链接：https://blog.csdn.net/mu_rain/article/details/80240296
http://www.zzvips.com/article/184402.html
页:
[1]