<?php
function fibonacci($n) {
static $prox = 3;
$cache[0] = 0;
$cache[1] = 1;
$cache[2] = 1;
if ($n < $prox) {
echo "cache -> "; //está aqui só para mostrar que entrou aqui
return $cache[$n];
}
for ($i = $prox; $i <= $n; $i++) {
$cache[$i] = $cache[$i - 1] + $cache[$i - 2];
}
echo $i - $prox . " passos -> "; //está aqui só para mostrar que entrou aqui
$prox = $n + 1;
return $cache[$n];
}
echo fibonacci(5) ."\n";
echo fibonacci(20) ."\n";
echo fibonacci(100) ."\n";
echo fibonacci(10) ."\n";
echo fibonacci(100) ."\n";
echo fibonacci(120) ."\n";
PD9waHAKZnVuY3Rpb24gZmlib25hY2NpKCRuKSB7CiAgICBzdGF0aWMgJGNhY2hlID0gYXJyYXkoKTsKICAgIHN0YXRpYyAkcHJveCA9IDM7CiAgICAkY2FjaGVbMF0gPSAwOwogICAgJGNhY2hlWzFdID0gMTsKICAgICRjYWNoZVsyXSA9IDE7CiAgICBpZiAoJG4gPCAkcHJveCkgewogICAgCWVjaG8gImNhY2hlIC0+ICI7IC8vZXN0w6EgYXF1aSBzw7MgcGFyYSBtb3N0cmFyIHF1ZSBlbnRyb3UgYXF1aQogICAgICAgIHJldHVybiAkY2FjaGVbJG5dOwogICAgfQogICAgZm9yICgkaSA9ICRwcm94OyAkaSA8PSAkbjsgJGkrKykgeyAKCSAgICAkY2FjaGVbJGldID0gJGNhY2hlWyRpIC0gMV0gKyAkY2FjaGVbJGkgLSAyXTsKICAgIH0KICAJZWNobyAkaSAtICRwcm94IC4gIiBwYXNzb3MgLT4gIjsgLy9lc3TDoSBhcXVpIHPDsyBwYXJhIG1vc3RyYXIgcXVlIGVudHJvdSBhcXVpCiAgICAkcHJveCA9ICRuICsgMTsKICAgIHJldHVybiAkY2FjaGVbJG5dOwp9CmVjaG8gZmlib25hY2NpKDUpIC4iXG4iOwplY2hvIGZpYm9uYWNjaSgyMCkgLiJcbiI7CmVjaG8gZmlib25hY2NpKDEwMCkgLiJcbiI7CmVjaG8gZmlib25hY2NpKDEwKSAuIlxuIjsKZWNobyBmaWJvbmFjY2koMTAwKSAuIlxuIjsKZWNobyBmaWJvbmFjY2koMTIwKSAuIlxuIjs=