PHP - 项目欧拉＃2

我得到了答案很好，但是当我运行下面的代码，PHP - 项目欧拉＃2


$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。

来源

2011-02-28 rubycon

比方说，$ I等于13.然后$x = fib(13)

现在的下一个迭代，$i等于14，并$x = fib(14)

现在，在下一次迭代中，$i = 15，所以我们必须计算$x。而$x必须等于fib(15)。现在，笏将是最便宜的方式来计算$x？

（我试图不给答案了，因为这会破坏拼图）

来源

2011-02-28 22:39:03 markijbema

仍然不确定。如果我们已经将fib（14）的值存储在x中，那么有一种方法不必通过fib（15）递归，但是使用x的值可以更快速地计算fib（15）？ – rubycon 2011-02-28 22:48:13

如果你还有fib（13）的值，该怎么办？ – markijbema 2011-02-28 22:54:58

啊，我明白你的意思了。是的，我重写了不使用递归函数的代码，并且加速了很多。 – rubycon 2011-02-28 23:03:32

-1

您最好将运行总数存储起来，并在算法结束时将其打印出来。

你也可以简化您的FIB（$ n）函数是这样的：

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

这将减少一些条件你需要经过相当。

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

来源

2011-02-28 22:38:44 dmcnelis

你误读了他的代码。当'x'等于或大于400万时，它**'break's **。 – 2011-02-28 22:40:05

你说得对，我误解了。 – dmcnelis 2011-02-28 22:42:28

谢谢，但上述功能是否有效？我在上面的例子中评估了fib（2）为0. – rubycon 2011-02-28 22:53:00

试试这个，在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
SYS 0m0.013s

来源

2011-02-28 22:39:21 azat

+1。Memoization是经典的斐波那契speeder-upper。 – 2011-02-28 22:41:09

仍然比这种情况下需要的更复杂。另外，我认为仅在需要指针时才提出Project Euler问题的解决方案是一种糟糕的风格。 – markijbema 2011-02-28 22:56:54

鉴于问题需要依次计算'fib（n）'，以这种方式缓存是浪费内存。 – 2011-03-01 00:54:35

-1

如果你真的想打印，当您去，用输出b uffer。在开始使用：

ob_start();

和所有执行后，使用

ob_flush(); 
    flush();

也可以增加你的暂停时以

set_time_limit(300); //the value is seconds... so this is 5 minutes.

来源

2011-02-28 22:40:18 FatherStorm

PHP - 项目欧拉＃2

回答

相关问题