PHP算法:斐波那契数列的N种算法
云栖号资讯:【点击查看更多行业资讯】
在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来!
前言
前段时间,遇到优化计算斐波那契数列的常规递归方法,但是一时间并没有及时想到很好的方法,所以后面查找了相关资料,总结了多种计算解法,所以分享出来,和大家一起交流学习。
斐波那契数是什么
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)。
知道了斐波那契数,那么下面我们就用多种不同的方法来计算获取第N位斐波那契数。
普通递归
这种方法是最常规的,直接根据定义F(n)=F(n - 1)+F(n - 2)递归计算即可,但是性能是最低的。
/** * 普通递归 * @param int $n * @return int */ function fib($n = 1) { // 低位处理 if ($n < 3) { return 1; } // 递归计算前两位 return fib($n - 1) + fib($n - 2); }
递归优化
从上面的递归方法可以看到,进行了很多的重复计算,性能极差,如果N越大,计算的次数太可怕了,那么,既然因为重复计算影响了性能,那么优化就从减少重复计算入手,即把之前计算的存储起来,这样就避免了过多的重复计算,优化了递归算法。
/** * 递归优化 * @param int $n * @param int $a * @param int $b * @return int */ function fib_2($n = 1, $a = 1, $b = 1) { if ($n > 2) { // 存储前一位,优化递归计算 return fib_2($n - 1, $a + $b, $a); } return $a; }
记忆化自底向上
自底向上通过迭代计算斐波那契数的子问题并存储已计算的值,通过已计算的值进行计算。使用for循环,减少递归带来的重复计算问题。
/** * 记忆化自底向上 * @param int $n * @return int */ function fib_3($n = 1) { $list = []; for ($i = 0; $i <= $n; $i++) { // 从低到高位数,依次存入数组中 if ($i < 2) { $list[] = $i; } else { $list[] = $list[$i - 1] + $list[$i - 2]; } } // 返回最后一个数,即第N个数 return $list[$n]; }
自底向上进行迭代
最低位初始化赋值,使用for从低位到高位迭代计算,从而得到第N个数。 /** * 自底向上进行迭代 * @param int $n * @return int */ function fib_4($n = 1) { // 低位处理 if ($n <= 0) { return 0; } if ($n < 3) { return 1; } $a = 0; $b = 1; // 循环计算 for ($i = 2; $i < $n; $i++) { $b = $a + $b; $a = $b - $a; } return $b; }
公式法
通过了解斐波那契序列和黄金分割比之间的关系,使用黄金分割率计算第N个斐波那契数。
/** * 公式法 * @param int $n * @return int */ function fib_5($n = 1) { // 黄金分割比 $radio = (1 + sqrt(5)) / 2; // 斐波那契序列和黄金分割比之间的关系计算 $num = intval(round(pow($radio, $n) / sqrt(5))); return $num; }
无敌欠揍法
这个方法,我就不多说了吧,大家都懂的,但是千万别轻易尝试……
/** * 无敌欠揍法 * @param int $n * @return int */ function fib_6($n = 1) { // 列举了30个数 $list = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269]; return $list[$n]; }
【云栖号在线课堂】每天都有产品技术专家分享!
课程地址:https://yqh.aliyun.com/live立即加入社群,与专家面对面,及时了解课程最新动态!
【云栖号在线课堂 社群】https://c.tb.cn/F3.Z8gvnK
原文发布时间:2020-07-08
本文作者:gxcuizy
本文来自:“掘金”,了解相关信息可以关注“掘金”
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
ES 规范为什么总在 6 月发版?
云栖号资讯:【点击查看更多行业资讯】在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来! 一.JavaScript 的诞生 1995 年 5 月,一个叫 Brendan Eich 的人花 10 天创造了 JavaScript 二.JavaScript 语言的标准化 最初 JavaScript 语言有 2 份标准: ECMA-262:主标准,由 ECMA 国际组织(Ecma International)负责管理 ISO/IEC 16262:第二标准,由国际标准化组织(ISO,International Organization for Standardization)和国际电子技术委员会(IEC,International Electrotechnical Commission)负责管理 出于商标版权的原因,规范标准中将这门语言称为 ECMAScript,所以原则上 JavaScript 与 ECMAScript 指的是同一个东西,但有时也会加以区分: JavaScript:指语言及其实现 ECMAScript:指语言标准及语言版本,比如 ES6 表示语言(标准)的第 6 版 ...
- 下一篇
无缝连接 dubbo-go 与 gRPC
最近我们dubbogo社区里面,呼声很大的一个feature就是对grpc的支持。在某位大佬的不懈努力之下,终于弄出来了。 今天我就给大家分析一下大佬是怎么连接dubbogo和grpc。 grpc 先来简单介绍一下grpc。它是google推出来的一个RPC框架。grpc是通过IDL(Interface Definition Language)——接口定义语言——编译成不同语言的客户端来实现的。可以说是RPC理论的一个非常非常标准的实现。 因而grpc天然就支持多语言。这几年,它几乎成为了跨语言RPC框架的标准实现方式了,很多优秀的rpc框架,如Spring Cloud和dubbo,都支持grpc。 server端 在go里面,server端的用法是: 它的关键部分是:s := grpc.NewServer()和pb.RegisterGreeterServer(s, &server{})两个步骤。第一个步骤很容易,唯独第二个步骤RegisterGreeterServer有点麻烦。为什么呢? 因为pb.RegisterGreeterServer(s, &s...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS8编译安装MySQL8.0.19
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Red5直播服务器,属于Java语言的直播服务器
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS6,CentOS7官方镜像安装Oracle11G