共计 1056 个字符,预计需要花费 3 分钟才能阅读完成。
斐波那契数列简略版:
<?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;
}
最终算法。
正文完