用php递归函数实现阶乘的计算(php求斐波那契数的两种实现方式递归与递推)
类别:编程学习 浏览量:1036
时间:2021-10-23 10:27:23 用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 [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
您可能感兴趣
- phpstudy服务器怎么设置(phpstudy本地环境开启.htaccess伪静态方法)
- iis6双php版本的设置(云主机IIS7.5支持PHP5.3以上版本和MYSQL)
- apache搭建php环境(Windows上安装Apache2、PHP5、MySQL5及与Resin配合实现多系统之整合)
- php回收机制(PHP session垃圾回收机制实例分析)
- php中row函数(PHP中number_format函数的用法讲解)
- php中怎么判断变量类型(PHP INT类型在内存中占字节详解)
- php逻辑技巧图解(php版本CKEditor 4和CKFinder安装及配置方法图文教程)
- php命名空间真的存在吗(PHP中命名空间的使用例子)
- phpstudy配置教程(phpStudy2018安装教程及本地服务器的配置方法)
- phpstudymysql启动又自动停止(Win下解决phpStudy MySQL启动失败)
- php单例设计方法(php设计模式之单例模式用法经典示例分析)
- thinkphp快速入门手册(从ThinkPHP3.2.3过渡到ThinkPHP5.0学习笔记图文详解)
- php把当前网页生成pdf(php转换上传word文件为PDF的方法基于COM组件)
- php中类的属性含义(php类中static与self的使用区别浅析)
- thinkphp5.1插件实现(Thinkphp5.0框架使用模型Model的获取器、修改器、软删除数据操作示例)
- php实现无cookie的session(php实现多站点共用session实现单点登录的方法详解)
- 超撩人治愈的绝美水彩,原来出自她之手 一笔一画令无数人沉醉(超撩人治愈的绝美水彩)
- 新手的勾线(新手的勾线)
- ()
- 书法欣赏 宋.志南诗《绝句》(宋.志南诗绝句)
- 每周一首古诗 《绝句》(每周一首古诗绝句)
- 蓝色代表什么(蓝色代表什么性格的人)
热门推荐
- C#文件读写的方法
- sql中的exists详解(SQL中EXPLAIN命令的使用方法)
- python redis锁的使用(Python操作redis实例小结String、Hash、List、Set等)
- phpstudy显示403(phpStudy配置多站点多域名方法及遇到的403错误解决方法)
- nginx配置详解(nginx请求限制配置方法)
- 12步轻松搞定python装饰器(Python3.5装饰器典型案例分析)
- php自定义函数返回多少个值(PHP7导出Excel报ERR_EMPTY_RESPONSE解决方法)
- python mysql配置(详解python校验SQL脚本命名规则)
- laravel 开发自定义组件(laravel实现上传图片并在页面显示的例子)
- zabbix监控数据库(利用zabbix监控ogg进程Windows平台)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9