PHP之斐波那契数列的N种算法

阅读量:26
2021-04-17
PHP之斐波那契数列的N种算法 (https://www.xwwx.net/) 主题模板 第1张

前言

前段时间,遇到优化计算斐波那契数列的常规递归方法,但是一时间并没有及时想到很好的方法,所以后面查找了相关资料,总结了多种计算解法,所以分享出来,和大家一起交流学习。

推荐:《PHP视频教程》

斐波那契数是什么

斐波那契数列(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;
}

无敌欠揍法

这个方法,我就不多说了吧,大家都懂的,但是千万别轻易尝试……

PHP之斐波那契数列的N种算法 (https://www.xwwx.net/) 主题模板 第2张
/**
 * 无敌欠揍法
 * @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种算法的详细内容,更多请关注星网无限其它相关文章!

声明:本文转载于:juejin,如有侵犯,请联系admin@删除

THE END

发表评论

相关推荐

  • 有关fgets()函数的文章推荐10篇

    以下正文:这篇文章主要介绍了PHP文件读写操作相关函数总结,本文总结了fwrite()、fread()、fgets()、fgetc()、file()、readf ...

    阅读量:65
    2021-04-19
  • php递归与无限分类实例详解

    这篇文章主要介绍了php实现递归与无限分类的方法,涉及php的递归操作技巧,需要的朋友可以参考下本文实例讲述了php实现递归与 ...

    阅读量:45
    2021-04-19
  • CI框架中zip类的使用

    CI框架自带的zip类简单实用,本文就来简单说一下ci框架的zip类的使用,需要的朋友可以参考下CI框架自带的zip类简单实用,本文 ...

    阅读量:43
    2021-04-18
  • SWFUpload插件上传文件的代码

    这篇文章主要介绍了文件上传之SWFUpload插件(代码),实现此代码主要分为两部分:1.前台文件和 2.后台文件upload.php,需要 ...

    阅读量:42
    2021-04-18
  • 关于destoon的URL Rewrite设置方法

    这篇文章主要介绍了destoon的URL Rewrite(伪静态)设置方法,需要的朋友可以参考下1、如果您的服务器支持.htaccess,则无需设 ...

    阅读量:47
    2021-04-18