C# -  Sequência de Fibonacci

  No artigo de hoje veremos como calcular a sequência de Fibonacci.

Tudo começou com  Leonardo de Pisa (Fibonacci=filius Bonacci=filho de Bonacci) matemático e comerciante da idade média, que em 1202 publicou um livro - Liber Abbaci -  onde descreveu o crescimento de uma população de coelhos , que viria trazer o conhecimento ao mundo ocidental dos números e seqüência que ficou conhecida como números de Fibonacci.

 

Mas quais seriam esses números e como obtê-los ?

Olhe com atenção a seqüência de números abaixo:

F = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,144, 233, ...

Repare que, exceto para os dois primeiros termos (1 e 1 ), todos os outros podem ser calculados iterativamente a partir da soma dos dois termos imediatamente anteriores.   

 

Assim o algoritmo para obter um número de Fibonacci pode ser expresso da seguinte forma:

M(1) = 1;
M(2) = 1;
M(n) = M(n-1) + M(n-2), para n > 2

A sequência de Fibonacci também pode ser observada em fenômenos naturais.  Confira abaixo alguns deles:

Girassol: o miolo do girassol possui sementes que são dispostas em um conjunto de espiral duplo. Na maioria das vezes são 21 no sentido horário e outras 34 em anti-horário.
 
Pinha: depois do crescimento da fruta, as sementes formam um duplo espiral com oito no sentido horário e outras 13 em anti-horário.

Concha do caramujo: cada parte da concha possui o tamanho da soma dos dois antecessor.Sabe-se que um conha apresenta três lados principais, então, supondo que um lado mede 2 (1 + 1), e outro 5 (3 + 2) o terceiro será 8 (5 + 3).
 
(fonte: https://www.educamaisbrasil.com.br/enem/matematica/sequencia-de-fibonacci)

Criando a sequência de Fibonacci

Um código C# bem simples para calcular a sequência de Fibonacci pode ser visto a seguir:

int elementoAtual = 0;
int proximoElemento = 1;
Console.WriteLine("\nSequência de Fibonacci");
Console.WriteLine("\nNúmero de elementos : \n");
var numeroElementos = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Elemento atual   : 0 ");
Console.WriteLine("Próximo Elemento : 1 ");
Console.WriteLine();
for (int i = 2; i <= numeroElementos; i++)
{
    int soma = elementoAtual + proximoElemento;
    Console.Write(soma + " ");
    elementoAtual = proximoElemento;
    proximoElemento = soma;
}
Console.ReadLine();

Neste programa, usamos NumeroElementos para representar o número total de elementos que queremos imprimir na série de Fibonacci. Usamos elementoAtual e proximoElemento para representar os elementos atuais e próximos da série, respectivamente.

Em seguida, usamos um loop for para iterar sobre os elementos restantes na série e calcular cada elemento adicionando os dois elementos anteriores, e,  a seguir imprimimos cada elemento à medida que o calculamos usando o método Console.Write().

Por fim, atualizamos os valores de elementoAtual e proximoElemento para a próxima iteração do loop.

A forma mais simplificada deste código poderia ser feita da seguinte forma:

Console.Write("Digite o número de termos que deseja gerar
na sequência de Fibonacci: ");

int n = int.Parse(Console.ReadLine());
int a = 0;
int b = 1;
for (int i = 0; i < n; i++)
{
    Console.Write("{0} ", a);
    int temp = a;
    a = b;
    b = temp + b;
}
Console.ReadLine();

Podemos escrever um código para gerar a sequência de Fibonacci usando a recursividade da seguinte forma:

Console.WriteLine("\nSequência de Fibonacci");
Console.WriteLine("\nNúmero de elementos : \n");
var numeroElementos = Convert.ToInt32(Console.ReadLine());
Console.Write($"\nA série de Fibonacci com {numeroElementos} termos é : \n\n");
for (int i = 0; i < numeroElementos; i++)
{
    Console.Write(Fibonacci(i) + " ");
}
Console.ReadKey();
static int Fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Para imprimir a série de Fibonacci até um determinado número em C# usando a abordagem baseada em um loop, podemos iterar pela sequência e imprimir cada número até atingirmos o valor desejado.

Console.Write("\nImprimir a sequêcia de Fibonacci até o número : ");
int numeroElementos = Convert.ToInt32(Console.ReadLine());
PrintFibonacci(numeroElementos);
Console.ReadKey();
static void PrintFibonacci(int n)
{
    int anterior = 0;
    int atual = 1;
    while (atual <= n)
    {
        Console.Write(atual + " ");
        int proximo = anterior + atual;
        anterior = atual;
        atual = proximo;
    }
}

Calcular o n-ésimo número de Fibonacci não é difícil, basta chegar ao valor com o índice correto.

Vamos primeiro dar uma olhada em uma abordagem iterativa. Aqui estamos usando um array de inteiros para manter os números de Fibonacci até n e retornando o enésimo número de Fibonacci.

Console.Write("Para qual número da sequência deseja obter o número  : ");
int numeroSequencia = int.Parse(Console.ReadLine());
var resultado = GetNumeroFibonacciParaNumero(numeroSequencia);
Console.WriteLine($"O valor para este termo é : {resultado}");
Console.ReadKey();
static int GetNumeroFibonacciParaNumero(int n)
{
    int numero = n - 1; 
    int[] Fib = new int[numero + 1];
    Fib[0] = 0;
    Fib[1] = 1;
    for (int i = 2; i <= numero; i++)
    {
        Fib[i] = Fib[i - 2] + Fib[i - 1];
    }
    return Fib[numero];
}

Outra possibilidade seria usar o código abaixo para obter o valor de um termo da sequência : 

static void GetValorTermo(int n)
{
    int a = 0;
    int b = 1;
    if (n == 1)
    {
        Console.WriteLine(a);
    }
    else if (n == 2)
    {
        Console.WriteLine(b);
    }
    else
    {
        for (int i = 3; i <= n; i++)
        {
            int c = a + b;
            a = b;
            b = c;
        }
        Console.WriteLine(b);
    }
}

Podemos assim ter diversas implementações para calcular a sequência de Fibonacci e suas variações.

E estamos conversados...

Referências:

José Carlos Macoratti