php求斐波那契数的两种实现方式【递归与递推】

yipeiwu_com6年前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[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相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结

希望本文所述对大家PHP程序设计有所帮助。

相关文章

php中文本操作的类

给大家一个简单的文本操作的类  我以前写的,不过一直都没机会用了,文本不如数据库 数据是以行保存的,以\n结尾,注意你输入的数据必须以"\n"结尾的,这是几个最基本的类成员,文...

php自动注册登录验证机制实现代码

php自动注册登录验证机制实现代码

背景: 在phpwind站点后台添加一个名为“广告管家”(广告管家为CNZZ的一款广告投放的应用)的应用,整个“广告管家”的应用是通过iframe载入,载入的具体内容根据不同站点显示针对...

深入php多态的实现详解

多态性是指相同的操作或函数、过程可作用于多种类型的对象上并获得不同的结果。不同的对象,收到同一消息将可以产生不同的结果,这种现象称为多态性。多态性允许每个对象以适合自身的方式去响应共同的...

PHP判断网络文件是否存在的方法

本文实例讲述了PHP判断网络文件是否存在的方法。分享给大家供大家参考。具体实现方法如下: $file = "//www.jb51.net/demo/file_exists.zip";...

PHP加速 eAccelerator配置和使用指南

前一段时间完成了服务器从FreeBSD4.10到6.1的升级,同时把PHP也升级到了最新的PHP5.1.4,Apache也升级到了最新的Apache2.2,为了更好的提高系统的性能考虑对...