大数斐波那契数列的算法

church -
大数斐波那契数列的算法

斐波那契数列简单版:

<?php

function fibonacci($n) {

    if ($n <= 1) {
        return $n;
    }

    return fibonacci($n-1) + fibonacci($n-2);
}

n小于10,性能尚可。n取大数,使用时间飙升。优化一下,空间换时间,已经计算出结果的存在数组里,复用。

<?php

function fibonacci($n) {
    static $cache = [];

    if (isset($cache[$n])) {
        return $cache[$n];
    }

    if ($n <= 1) {
        return $n;
    }

    $temp = fibonacci($n-1) + fibonacci($n-2);
    $cache[$n] = $temp;
    return $temp;
}

现在性能是够了,但是如果n取的数特别大,超出整型或浮点型的范围,那就要改用字符串存储。要实现竖式加法。

<?php
function fibonacci($n) {
    static $cache = [];

    if (isset($cache[$n])) {
        return $cache[$n];
    }

    if ($n <= 1) {
        return $n;
    }

    $temp = stringAdd(fibonacci($n-1), fibonacci($n-2));
    $cache[$n] = $temp;
    return $temp;
}

function stringAdd($s1, $s2) {
    $s1 = strval($s1);
    $s2 = strval($s2);
    $s1Length = strlen($s1);
    $s2Length = strlen($s2);
    $length = 0;

    if ($s1Length > $s2Length) {
        $length = $s1Length;
        $s2 = str_pad($s2, $s1Length, '0', STR_PAD_LEFT);
    } else {
        $length = $s2Length;
        $s1 = str_pad($s1, $s2Length, '0', STR_PAD_LEFT);
    }

    $returnRes = '';
    $carry = 0;
    for ($i=$length-1; $i>=0; $i--) {
        $result = intval($s1[$i]) + intval($s2[$i]) + $carry;
        $res = $result % 10;
        $carry = floor($result / 10);

        $returnRes = $res . $returnRes;
    }

    if ($carry > 0) {
        return strval($carry) . $returnRes;
    }

    return $returnRes;
}

最终算法。

特别申明:本文内容来源网络,版权归原作者所有,如有侵权请立即与我们联系(cy198701067573@163.com),我们将及时处理。

php介绍

PHP即“超文本预处理器”,是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言,与C语言类似,是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习,使用广泛,主要适用于Web开发领域。
上一篇: ModStart快速CRUD

Tags 标签

php算法

扩展阅读

加个好友,技术交流

1628738909466805.jpg