PHP -项目Euler #2

Question

我得到了很好的答案，但是当我运行以下代码时，

$total = 0;
$x = 0;

for ($i = 1;; $i++)
{
    $x = fib($i);

    if ($x >= 4000000)
        break;
    else if ($x % 2 == 0)
        $total += $x;

    print("fib($i) = ");
    print($x);
    print(", total = $total
");
}

function fib($n)
{
    if ($n == 0)
        return 0;
    else if ($n == 1)
        return 1;
    else
        return fib($n-1) + fib($n-2);
}

我收到警告，我已经超过了30秒的最大执行时间。你能给我一些关于如何改进这个算法的指点吗，或者关于代码本身的指点？顺便说一句，这个问题是here提出的。

Answer 1

假设$i等于13。然后$x = fib(13)

现在在下一次迭代中，$i等于14，$x = fib(14)

现在，在下一次迭代中，我们必须计算$x。并且$x必须等于fib(15)。现在，wat是计算$x的最便宜的方法

(我尽量不给出答案，因为那会毁了这个谜题)

Answer 2

尝试一下，在fib中添加缓存

<?

$total = 0;
$x = 0;

for ($i = 1;; $i++) {
    $x = fib($i);

    if ($x >= 4000000) break;
    else if ($x % 2 == 0) $total += $x;

    print("fib($i) = ");
    print($x);
    print(", total = $total\n");
}

function fib($n) {
    static $cache = array();
    if (isset($cache[$n])) return $cache[$n];

    if ($n == 0) return 0;
    else if ($n == 1) return 1;
    else {
        $ret = fib($n-1) + fib($n-2);
        $cache[$n] = $ret;
        return $ret;
    }
}

时间：

实数0m0.049s

用户0m0.027s

系统0m0.013s

Answer 3

您最好存储运行总数，并在算法的末尾打印它。

你也可以像这样简化你的fib($n)函数：

function fib($n)
{
    if($n>1)
      return fib($n-1) + fib($n-2);
    else
      return 0;
}

这将大大减少你需要经历的条件的数量。

**现在编辑，我重新阅读了问题**