本文实例讲述了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
1
2
3
4
5
6
7
8
|
//使用递归方式求斐波那契数
public function fb( $n ){ //
if ( $n <=2){
return 1;
} else {
return fb( $n -1) + fb( $n -2);
}
}
|
2使用递推方法。
1
2
3
4
5
6
7
8
9
10
11
12
|
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),实测代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/**性能测试。*/
function bench_profile( $starttime , $flag = '' ){
$endtime = explode ( ' ' ,microtime());
$thistime = $endtime [0]+ $endtime [1]-( $starttime [0]+ $starttime [1]);
$thistime = round ( $thistime ,3);
return $flag . "-bench:" . $thistime . " sec" ;
}
//使用递归算法。
ini_set ( "max_execution_time" ,3600);
$s = explode ( ' ' ,microtime());
echo bench_profile( $s ). "<br/>" ;
echo fb(35); //使用递归 耗时 40.925 sec 每往上一个数约慢两倍
echo bench_profile( $s ). "<br/>" ;
//使用递推算法。
$s = explode ( ' ' ,microtime());
echo bench_profile( $s ). "<br/>" ;
echo fb2(35); //使用递推 时间极短。
echo bench_profile( $s ). "<br/>" ;
|
总结:使用递归算法,到求第100 个斐波那契数 时会卡到机器跑不动,而使用递推算法,几乎不费时间。
算法复杂度是非常重要的概念,也是区分程序员的一把好尺子。
希望本文所述对大家PHP程序设计有所帮助。
原文链接:https://blog.csdn.net/mu_rain/article/details/80240296