PHP之斐波那契数列的N种算法-php教程

媒介

前段工夫，遇到优化较量争论斐波那契数列的惯例递归办法，然而一工夫并无实时想到很好的办法，以是前面查找了相干材料，总结了多种较量争论解法，以是分享进去，以及各人一同交流学习。

保举：《PHP视频教程》

斐波那契数是甚么

斐波那契数列（Fibonacci sequence），又称黄金宰割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁衍为例子而引入，故又称为“兔子数列”，指的是这样一个数列：一、一、二、三、五、八、1三、2一、3四、……正在数学上，斐波那契数列以以下被以递推的办法界说：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];
}

最初

好了，我就大略写了几种解法，假如有不合错误之处，请各人指出，我会实时修正，各人有其余较量争论办法，欢送分享进去一同交流以及学习，谢谢！

以上就是PHP之斐波那契数列的N种算法的具体内容，更多请存眷资源魔其它相干文章！