关于php:大数斐波那契数列的算法

斐波那契数列简略版:

<?phpfunction fibonacci($n) {    if ($n <= 1) {        return $n;    }    return fibonacci($n-1) + fibonacci($n-2);}

n小于10，性能尚可。n取大数，应用工夫飙升。优化一下，空间换工夫，曾经计算出后果的存在数组里，复用。

<?phpfunction 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取的数特地大，超出整型或浮点型的范畴，那就要改用字符串存储。要实现竖式加法。

<?phpfunction 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;}

最终算法。