Fibonacci sequence

Asked

Viewed 4,638 times

14

I need to perform an exercise to show the Fibonacci sequence up to the 100th element, I need to create a Fibonacci function that should receive the element index and the function will calculate the corresponding number of that index.

I’m currently performing like this, but I’d like to know where I’m going wrong?

follows the code:

$sequence = array();

for ($i=1; $i <= 100 ; $i++) { 
    if ($i < 2) {
        $sequence[$i] = $i;         
    } else{
        $sequence[$i] = $sequence[$i - 1] + $sequence[$i - 2];          
    }       
}

function fibonacci($n){

    echo $sequence[$n];

};

fibonacci(100);
php fibonnaci

2 answers

14


One problem I found was your IF not skip the first 2 numbers, see the subtle difference:

$sequence = array();

for ( $i = 1; $i <= 100 ; $i++) { 
    if ($i <= 2) { // Ou começa $i de 0, ou usa "<=" aqui em vez do "<"
        $sequence[$i] = $i;         
    } else{
        $sequence[$i] = $sequence[$i - 1] + $sequence[$i - 2];          
    }       
}

function fibonacci($n){
    global $sequence;
    echo $sequence[$n];

};

fibonacci(100);

In addition, I added this line:

global $sequence;

because, within a function, the scope is different. Without the global, the $sequence that you are trying to display within the function is a new variable, not the same set outside.

Maybe it would be better this way, starting from zero, because in the above option, we are with offset of 1 in formula:

for ($i = 0; $i <= 100 ; $i++) { 
   if ( $i < 2 ) {

See working on IDEONE.


A leaner alternative

One way would be to simplify the code and calculate the numbers only in the call. The use of array pre-calculated only makes sense if you know you will need several values:

function fibonacci($n) {
    $a = 0;
    $b = 1;
    $c = 1;
    for ($i = 1; $i < $n ; $i++) { 
        $c = $a + $b;
        $a = $b;
        $b = $c;
    }
    return $c;
}
echo fibonacci(100) ."\n";

The downside of this is that every time you need a number, you’re reworking the whole calculation. The advantage is that if it is a large number, will spend time, but need not store in memory (of course with large numbers will start to have shunting problems and even overflow, in any of the functions)

See this version on IDEONE.


Mathematical formula

Since it is an exercise, the ideal solution is the above loop, and for the calculation of several numbers, the summed loop is simpler for the machine to process. But if any reader came here needing to calculate any of the numbers in the series, there is a "direct" way to get the result:

Fn = [ Phi n - (phi)n ]/Sqrt[5]

I mean, Fn = [ Phin - (Phi)n ] / Sqrt(5), of which Phi is (1+Sqrt(5))/2, and Phi is -1/Phi, we can do this:

function fibonacci( $n ) {
   $V5   = sqrt( 5 );
   $Phi  = ( 1 + $V5 ) / 2;
   $iPhi = -1 / $Phi;
   return round( ( pow( $Phi, $n ) - pow( $iPhi, $n ) ) / $V5 );
}

See working on IDEONE.

Read more on Wikipedia about:

  • For those using the formula with φ and Φ: Just to remember there will be precision problem using floating point, since root 5 is not representable in a finite number of binary boxes. This problem should only happen when n is sufficiently large. And, another fun point, the analytical resolution of this potentiation always leads to the annulment of all root factors of 5 that are not elevated to even number, then the answer at all times is whole

1

function fibonacci($numero_limite):array
{
    $matriz = [0,1];

    for($i=1;$i<$numero_limite;$i++)
    {
        array_push($matriz, $matriz[$i]+$matriz[$i-1]);
    }
    return $matriz;
}

//Example of use;

print_r(fibonacci(10));

//Return

Array ( [0] => 0 [1] => 1 [2] => 1 [3] => 2 [4] => 3 [5] => 5 [6] => 8 [7] => 13 [8] => 21 [9] => 34 [10] => 55 )

Browser other questions tagged php fibonnaci

You are not signed in. Login or sign up in order to post.