Fibonacci Sequence

Question

Fibonacci Sequence

Navigation

#1 by (12 votes)

12

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

I'm currently doing this, but would like to know where I'm going wrong?

follow 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

asked by anonymous 15.12.2015 / 04:01

1 answer

How do I pass one parameter to another scope with angularjs? What is the difference between props and state in React.js?

score 12 · Accepted Answer

One problem I encountered was your IF did 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 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 have offset of 1 in the formula:

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

See working at IDEONE .

A leaner alternative

One way would be to simplify the code and calculate the numbers only in the call. Using pre-compiled array only makes sense if you know you're going to need multiple 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 to this is that every time you need a number, you are redoing the whole calculation. The advantage is that if it is a large number, it will take time, but it does not need to be stored in memory (of course with large numbers it will start to have deviation problems and even overflow in any of the functions)

See this version on IDEONE .

Mathematical Formula

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

Thatis,Fn=[Phin-(phi)n]/Sqrt(5),wherePhiis(1+Sqrt(5))/2,andphiis-1/Phi,wecandothis:

functionfibonacci($n){$V5=sqrt(5);$Phi=(1+$V5)/2;$iPhi=-1/$Phi;returnround((pow($Phi,$n)-pow($iPhi,$n))/$V5);}

SeeworkingatIDEONE.

ReadmoreonWikipediaabout:

Fibonacci sequence (currently English content is better).
Golden ratio