斐波那契数列的N种算法
算法 数列 那契 斐波
2023-06-13 09:11:39 时间
什么是斐波那契数列
斐波那契数列(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*)。
普通递归(算法一)
这种方法是最常规的,直接根据定义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];
}
版权说明
本文转自 PHP中文网 ,原文名称:《PHP之斐波那契数列的N种算法》
如无特殊说明《斐波那契数列的N种算法》为博主MoLeft原创,转载请注明原文链接为:https://moleft.cn/post-163.html
相关文章
- shift+window+s_Dijkstra算法
- python生兔子问题(递归算法)_java实现斐波那契数列
- 老生常谈React的diff算法原理-面试版
- 最小生成树——普里姆算法(prim)
- 算法详解 - 神奇的兔子数列
- js斐波那契数列递归算法_php斐波那契数列递归算法
- 论文拾萃 | PISTS算法求解obnoxious p-median problem (附Python代码)
- SC-FDE(单载波频域均衡)实际应用中均衡算法的影响
- [随笔]文件系统上存储哈希对象:哈希算法以及目录结构对性能的影响
- 算法-斐波那契数列的三种算法以及复杂度详解编程语言
- C语言除法算法和取模运算的实现(多种算法,多种思路)
- 红色闪电推荐算法的打破极限(redis随机推荐算法)
- Redis通过复制算法实现数据复制(redis通过什么复制)
- 预告:从传感器和算法原理讲起,机器人是如何避障的丨硬创公开课
- 检测CSAM的儿童安全算法NeuralHash可能被操纵?苹果回应:非同个版本
- JS维吉尼亚密码算法实现代码
- 组合算法的PHP解答方法
- php常用算法和时间复杂度