php求斐波那契数的两种实现方式递归与递推介绍
发布时间：2022-06-28 03:44:25 所属栏目：PHP教程 来源：互联网
导读：本文实例讲述了php求斐波那契数的两种实现方式，分享给大家供大家参考，具体如下： 斐波那契数，亦称之为斐波那契数列（意大利语： Successione di Fibonacci)，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：1、1、2、3、5
|
本文实例讲述了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使用递推方法。 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[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 个斐波那契数 时会卡到机器跑不动，而使用递推算法，几乎不费时间。 2 使用递归方法。 顺着思路去想， 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); } } 算法复杂度是非常重要的概念，也是区分程序员的一把好尺子。 （编辑：我爱故事小小网_铜陵站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330570号