Page 1 of 1

FIBONACCI SERIES

Posted: Mon Jul 27, 2009 4:53 am
by bluekhille
Can any body help me with this one?

i need a program.

sample output

if i input 5 then the output must be

1
1
2
3
5


my input is the number of alteration
then the output is the sum of two numbers above it. out depends on number of alteration.

pls help me thanks!

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 5:02 am
by VladSun
Google is your friend :)
http://www.google.com/search?client=ope ... 8&oe=utf-8

Though, I really think you should try to implement it by yourself.

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 5:07 am
by bluekhille
thanks vlad! :D

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 5:44 am
by jackpf
Just to let everyone know that I'm such mathematical genius :P

Code: Select all

<?php
        //the initial number :)
        $number = 40;
       
        //the two integers required for the fibonacci sequence
        $i  = 0;
        $ii = 1;
        //the counter to alternate sums
        $counter = 0;
        //init the sequence
        $sequence = array(0, 1);
       
        //while the sum of each fibonacci number is less than the initial number...
        while($i + $ii <= $number)
        {
                //just to save me some typing
                $_i = $i + $ii;
               
                //append to the sequence
                array_push($sequence, $_i);
               
                //alternate which integer has the previous added to it (must start with 0 + 1 since 1 + 0 will cause an infinite loop)
                if($counter % 2 == 0)
                        $i  += $ii;
                else
                        $ii += $i;
               
                //increment counter
                $counter++;
        }
       
        echo implode(', ', $sequence);
?>

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 5:54 am
by jayshields
Basically stay away from recursion with this algorithm, although the code is much more concise the performance degrades hugely when the number is anything substantial.

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 6:06 am
by VladSun
jackpf wrote:

Code: Select all

 
                $_i = $i + $ii;
               
                array_push($sequence, $_i);
               
                if($counter % 2 == 0)
                        $i  += $ii;
                else
                        $ii += $i;
               
                $counter++;
 
Why do you need this?
According to Fibonacci series definition, it should be:

Code: Select all

 
                $_i = $i + $ii;
               
                array_push($sequence, $_i);
           
                $i  = $ii;
                $ii = $_i;
               

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 7:33 am
by bluekhille
so which is the right one? :?

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 7:59 am
by VladSun
VladSun wrote:Though, I really think you should try to implement it by yourself.

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 8:41 am
by jackpf
jayshields wrote:Basically stay away from recursion with this algorithm, although the code is much more concise the performance degrades hugely when the number is anything substantial.
How are you supposed to do this without recursion?

And I doubt that. With the number 23452346234623464294967296 it takes 0.00018310546875 seconds to execute on my PC.
VladSun wrote:According to Fibonacci series definition, it should be:

Code: Select all

 
                $_i = $i + $ii;
               
                array_push($sequence, $_i);
           
                $i  = $ii;
                $ii = $_i;
               
And yeah, you're right. Although they both work. I haven't studied the fibonacci sequence for years though :P

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 8:50 am
by jayshields
Your version isn't recursive.

The recursive version is the most concise version, which seems to be the version most people are introduced to. It looks like this:

Code: Select all

function fib($num)
{
  //Base case
  if($num < 2)
    return $num;
 
  return fib($num - 1) + fib($num - 2);
}
OP: The first Google result for "fibonacci php" gives http://snipplr.com/view/1993/php-fibonacci-sequence/ which seems a pretty good solution to me.

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 9:00 am
by jackpf
Oh right, I thought you were referring to my while() loop as recursion :) Yeah, that probably would be slower.

And yeah, there are loads on google. Still, it was a nice challenge though :P

Re: FIBONACCI SERIES

Posted: Mon Jul 27, 2009 9:34 am
by VladSun
Also, a full version should implement calculation of Fibonacci series with negative numbers:

F(-n) = F(n)(-1)^(n+1)