PHP - Project Euler #2

I got the answer fine, but when I run the following code,

$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);
}

I get the warning that I have exceeded the maximum execution time of 30 seconds. Could you give me some pointers on how to improve this algorithm, or pointers on the code itself? The problem is presented here, by the way.

Let's say $i equal to 13. Then $x = fib(13)

Now in the next iteration, $i is equal to 14, and $x = fib(14)

Now, in the next iteration, $i = 15, so we must calculate $x. And $x must be equal to fib(15). Now, wat would be the cheapest way to calculate $x?

(I'm trying not to give the answer away, since that would ruin the puzzle)

Try this, add caching in 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;
    }
}

Time:
real 0m0.049s
user 0m0.027s
sys 0m0.013s

You'd be better served storing the running total and printing it at the end of your algorithm.

You could also streamline your fib($n) function like this:

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

That would reduce the number of conditions you'd need to go through considerably.

** Edited now that I re-read the question **

If you really want to print as you go, use the output buffer. at the start use:

ob_start();

and after all execution, use

ob_flush();
    flush();

also you can increase your timeout with

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