Fibonacci sequence does not work

Question

I’m having trouble exiting the Fibonacci sequence and I can’t identify where the bug is. Here’s the code:

#include <stdio.h>
#include <stdlib.h>

int main(){

int i, Fib[100], n;

scanf("%d",&n);

printf("0 ");

for(i=0;i<n-1;i++){

    if(i == 0){
    Fib[i]=0;
    }
    if(i==1 || i==2){
        Fib[i] = 1;
    }
    else{
        Fib[i] = Fib[i-1] + Fib[i-2];
    } 
}

for(i=0;i<n-1;i++){
    printf("%d ",Fib[i]);
}

return 0;
}

Answer 1

The reason I was wrong is that the logic is too complex. Following the definition of Fibonacci makes it simpler.

The definition states that the sequence begins with 0 and 1, so start the sequence with 0 and 1 explicitly. After that you don’t need to treat anything, you don’t need to condition what you’re going to do. It gets simpler and faster.

The definition does not speak in a sequence that has exceptions in certain elements. Define the problem correctly and the solution comes out more fluid.

I kept the array because it might be a requirement, but it is completely unnecessary to just print a Fibonacci sequence.

#include <stdio.h>

int main() {
    int fib[100];
    int n;
    scanf("%d", &n);
    fib[0] = 0;
    fib[1] = 1;
    n--;
    for (int i = 2; i < n; i++) fib[i] = fib[i - 1] + fib[i - 2];
    for (int i = 0; i < n; i++) printf("%d ", fib[i]);
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

Answer 2

The second conditional block was incorrect, because the variable i was different from 1 or 2 would enter the else, so Fib[0] was wrong.

#include <stdio.h>
#include <stdlib.h>

int main(){

    int i, Fib[100], n;

    scanf("%d",&n);

    for(i = 0; i < n; i++){
        if(i == 0){
            Fib[i] = 0;
        } 
        else if(i == 1 || i == 2){
            Fib[i] = 1;
        }
        else{
            Fib[i] = Fib[i-1] + Fib[i-2];
        }
        printf("Fib[%d] = %d \n", i, Fib[i]);
    }

    return 0;
}

Answer 3

You can work with the type unsigned long long which has the size of 64bits, making it possible to generate Fibonacci sequences of up to 91 numbers:

#include <stdio.h>
#include <stdlib.h>

#define MAX_FIBO_SEQ   (91)

typedef unsigned long long uint64_t;  /* ( (2^64) - 1 ) = 18.446.744.073.709.551.615 max. */

int fibonacci( uint64_t f[], int n )
{
    int i = 0;

    if( n <= 0 )
        return -1;

    if( n > MAX_FIBO_SEQ )
        n = MAX_FIBO_SEQ;  /* Nao permite overflow */

    f[0] = 1;

    if( n == 1 )
        return n;

    f[1] = 1;

    if( n == 2 )
        return n;

    for( i = 2; i < n; i++ )
        f[i] = f[i - 2] + f[i - 1];

    return n;
}


int main( int argc, char * argv[] )
{
    int i = 0;
    int n = atoi(argv[1]);
    uint64_t seq[ MAX_FIBO_SEQ ];

    /* Preenche array 'seq' com uma sequencia dos 'n' primeiros
       numeros da serie de Fibonacci... */
    n = fibonacci( seq, n );

    /* Exibe array */
    for( i = 0; i < n; i++ )
        printf("%s%lld", (i)?", ":"", seq[i] );
    printf("\n");

    return 0;
}

Test #1:

$ ./fibo 10
1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Test #2:

$ ./fibo 91
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309