用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
您可能感兴趣
- php 精度误差调整(php精度计算的问题解析)
- php常用执行函数(PHP自动载入类文件函数__autoload的使用方法)
- phpstudy的默认网站根目录是什么(phpstudy v8.0创建本地站点域名教程图文)
- php内置加密函数(php过滤htmlspecialchars 函数实现把预定义的字符转换为 HTML 实体用法分析)
- 如何解决php跨域问题(php简单检测404页面的方法示例)
- 自己在做项目过程中的php知识(PHP+Oracle本地开发环境搭建方法详解)
- phpcurl调用本地函数(PHP使用CURL实现下载文件功能示例)
- phpzip压缩原理(PHP生成zip压缩包的常用方法示例)
- php面向对象final怎么设置(PHP面向对象程序设计中的self、static、parent关键字用法分析)
- php生成安全随机数(PHP随机数函数rand与mt_rand的讲解)
- php设计模式学习(PHP设计模式之PHP迭代器模式讲解)
- php微信支付步骤(PHP实现微信提现企业付款到零钱)
- php wamp 环境搭建(wamp服务器访问php非常缓慢的解决过程)
- thinkphp中view视图的作用(Thinkphp5.0框架视图view的模板布局用法分析)
- php把当前网页生成pdf(php转换上传word文件为PDF的方法基于COM组件)
- php对象模型(PHP数据对象映射模式实例分析)
- 泰剧《爱欲之神》Boom kitkong和Great合体杂志(泰剧爱欲之神Boomkitkong和Great合体杂志)
- 素人恋爱综艺火药味十足 男生为赢得芳心集体扯头花,真是出好戏(素人恋爱综艺火药味十足)
- 《囧妈》为何受抵制 春节七部影片撤档背后的责任与博弈(囧妈为何受抵制)
- 提醒 2019年起河南驾考要开设科目五 官方回应来了(2019年起河南驾考要开设科目五)
- 省 市书法家协会 送万福进万家 活动走进禹州美丽乡村(省市书法家协会)
- 点赞 禹州苌庄正式撤乡建镇 未来发展不可估量(禹州苌庄正式撤乡建镇)
热门推荐
- mysql怎么迁移数据(如何把本地mysql迁移到服务器数据库)
- C#中抽象类和接口的区别有哪些
- dedecms如何使用标签(DEDECMS首页调用最新评论和评论链接地址静态化实现代码)
- python中如何限制数字的个数(python 处理数字,把大于上限的数字置零实现方法)
- 安全进入docker容器的方法(使用docker部署一个简单的c/c++程序的方法)
- 注册会员信息管理(如何验证会员系统中用户的邮箱是否真实存在)
- centos搭建sftp服务器(Linux云服务器搭建SFTP服务器图片服务器的操作)
- php使用yield处理并发(Yii2.0框架模型多表关联查询示例)
- vue实现图片上传数据库(vue.js根据图片url进行图片下载)
- 阿里云主机Windows 2008 32位 64位自助正版激活图文教程(阿里云主机Windows 2008 32位 64位自助正版激活图文教程)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9