PHP算法：斐波那契数列各种算法代码的实现

遇到了优化斐波那契数列计算的常规递归方法，但没有及时想到好的方法，所以后来查找了相关资料，总结了一下它。我开发了多种计算方案，所以分享给大家，一起交流学习。

什么是斐波那契数

斐波那契数列又称黄金分割数列，是由数学家列昂纳多·斐波那契（莱昂纳多·斐波那契）以兔子饲养为例介绍的，所以又被称为“兔子数列”到这样一个数列： 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第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];
}

作者：gxcuizy
链接：https://juejin.im/post/6847902221128957965
来源：掘金
版权归作者所有。商业转载请联系作者获取授权。非商业转载请注明出处。