本文實例講述了php求斐波那契數(shù)的兩種實現(xiàn)方式。分享給大家供大家參考，具體如下：
斐波那契數(shù)，亦稱之為斐波那契數(shù)列（意大利語： Successione di Fibonacci)，又稱黃金分割數(shù)列、費波那西數(shù)列、費波拿契數(shù)、費氏數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞歸的方法定義：F0=0，F(xiàn)1=1，F(xiàn)n=Fn-1+Fn-2（n>=2，n∈N*），用文字來說，就是斐波那契數(shù)列列由 0 和 1 開始，之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加。
1 使用遞歸方法。 順著思路去想， f(1)= 1; f(2) = 1 ; f(3) = f(2)+f(1) 【2】 f(4) = f(3)+f(2) 3
//使用遞歸方式求斐波那契數(shù)
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;
}
最后，進行性能分析。
明顯的可以預(yù)測，遞歸方法，每多一層，就要向下遞歸兩次。 約為 O(2 的N次方) 而遞推算法為 O(n),實測代碼如下。
/**性能測試。*/
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 每往上一個數(shù)約慢兩倍
echo bench_profile($s )."br/>";
//使用遞推算法。
$s = explode(' ',microtime());
echo bench_profile($s )."br/>";
echo fb2(35); //使用遞推 時間極短。
echo bench_profile($s )."br/>";
總結(jié)：使用遞歸算法，到求第100 個斐波那契數(shù) 時會卡到機器跑不動，而使用遞推算法，幾乎不費時間。
算法復(fù)雜度是非常重要的概念，也是區(qū)分程序員的一把好尺子。
更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運算技巧總結(jié)》
希望本文所述對大家PHP程序設(shè)計有所幫助。
您可能感興趣的文章:- php菜單/評論數(shù)據(jù)遞歸分級算法的實現(xiàn)方法
- PHP實現(xiàn)無限極分類的兩種方式示例【遞歸和引用方式】
- PHP利用遞歸函數(shù)實現(xiàn)無限級分類的方法
- PHP自定義遞歸函數(shù)實現(xiàn)數(shù)組轉(zhuǎn)JSON功能【支持GBK編碼】
- PHP遞歸寫入MySQL實現(xiàn)無限級分類數(shù)據(jù)操作示例
- PHP數(shù)組遞歸排序?qū)崿F(xiàn)方法示例
- PHP迭代與遞歸實現(xiàn)無限級分類
- PHP實現(xiàn)遞歸的三種方法
