Sequência de Fibonacci

Esse post é sobre a resolução de uma situação problema usando C.  No código são utilizadas as funções mais básicas da linguagem. Este é um bom exemplo para a aplicação do uso de vetores. Ao longo do post explico o funcionamento do programa e no final está o código para acompanhar a explicação.

Descrição do problema

Em matemática, a Sucessão de Fibonacci (também Sequência de Fibonacci), é uma sequência de números inteiros, começando normalmente por 0 e 1, na qual, cada termo subsequente (numero de Fibonacci) corresponde a soma dos dois anteriores.

fonte: Wikipédia

Essa definição indica que precisamos de apenas 2 números inteiros, que são os valores iniciais, para montar a sequência. Sabemos também que essa sequência se segue infinitamente, portanto precisamos definir um valor máximo, ou o número de termos que se deseja calcular.

Para este exemplo escolhi os seguintes parâmetros:

  • Primeiro termo=0
  • Segundo termo=1
  • O programa para de calcular quando a sequência ultrapassa 1200.

Construção do programa

O funcionamento do programa se baseia em 2 itens:

  • Um vetor que armazena os valores já calculados da sequência(chamado “vetor“).
  • Uma variável que conta o índice do vetor (chamada “i“).

Dessa forma o vetor[0] (leia vetor de índice 0) é o primeiro número da sequência, e definimos que ele vale 0.  Assim como o vetor[1] é o segundo número da sequência, e vale 1 por definição. Logo, o primeiro número que o programa vai ter que calcular efetivamente é o vetor[2] = vetor[0]+vetor[1].

Note que a variável “i” conta o índice atual do vetor. Então o programa deve calcular vetor[i-1]+vetor[i-2] para obter o novo número da sequência, onde i-1 é o índice anterior ao atual e i-2 é o índice que podemos chamar de “anterior ao anterior”.  Dessa forma o programa já sabe como calcular a sequência, mas ele ainda não sabe quando deve parar de calcular.

Lembre-se que escolhemos que o valor limite era 1200, portanto, ao passar desse valor o programa deve entender já pode parar de calcular.  Mas de fato qual valor devemos checar para ver se passou de 1200? Em tese seria o vetor[i]  que é o valor atual do vetor. Porém, observando o código abaixo, verifica-se  que no final do while que calcula o valor atual, o programa já soma 1 na variável “i“, assim o valor atual já passa a ser o valor passado.  Portanto, devemos checar se o valor passado, que é o vetor[i-1], já chegou em 1200.

Além disso, ao final do cálculo da sequência o programa mostra até qual índice do vetor a sequência chegou. É importante salientar que o índice não representa o número de termos, mas sim o número de termos menos 1. Pois o índice começa em zero, e uma possível contagem de termos começaria em 1. Logo, se quiséssemos saber o número de termos, o programa deveria mostrar índice +1.

#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int main()
{
    int vetor[MAX];
    int i=2;

    vetor[0]=0;
    vetor[1]=1;

    printf("%d\n\n", vetor[0]);
    printf("%d\n\n", vetor[1]);

    while (vetor[i-1] < 1200)
    {
        vetor[i]=vetor[i-2]+vetor[i-1];
        printf ("%d\n\n",vetor[i]);
        vetor[i-2]=vetor[i-1];
        i++;
    }

    printf("a sequencia parou no indice %d",i-1);

    return 0;
}

Abraços galera, espero que tenham gostado!
Luíza Corrêa.