Sequência de Fibonacci


Leonardo Fibonacci

Leonardo Fibonacci, matemático italiano (Pisa, c. 1170 — c. 1250).ele ficou conhecido pela sequência de Fibonacci e pelo seu papel na introdução dos algorismos arábicos na Europa.
Ao reconhecer que a aritmética, com algarismos arábicos, era mais simples e eficiente do que com os algarismos romanos, Fibonacci viajou por todo o mundo mediterrâneo, chegando até Constantinopla, para estudar com os matemáticos árabes mais importantes de então, alternando os estudos com a atividade comercial.
Seus estudos foram tão importantes que até hoje existe uma publicação periódica, Fibonacci Quarterly inteiramente dedicada à sequência aritmética elaborada por ele.
Ele, propôs no século XIII, a sequência numérica abaixo:
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...)
Essa sequência tem uma lei de formação simples: cada elemento, a partir do terceiro, é obtido somando-se os dois anteriores. Veja: 1+1=2, 2+1=3, 3+2=5 e assim por diante.
Veja um exemplos de sua aplicação.
A partir de dois quadrados de lado 1, podemos obter um retângulo de lados 2 e 1. se adicionarmos a esse retângulo um quadrado de lado 2, obtemos um novo retângulo 3x2. Se adicionarmos agora um quadrado de lado 3, obtemos um retângulo 5x3. Observe a figura a seguir e veja que os lados dos quadrados que adicionamos para determinar os retângulos formam a sequência de Fibonacci.



Se utilizarmos um compasso e traçarmos o quarto de circunferência inscrito em cada quadrado, encontraremos uma espiral formada pela concordância de arcos cujos raios são os elemento da seqüência de Fibonacci.




Sequencia de Fribonacci



Essa sequência é definida como recursiva. Sendo Fn  os termos dessa sequência que são chamados de números de Fibonacci.  Aqui vão os primeiros termos dessa sequência:

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


Código em Pascal

Program Pzim ;
  Uses Crt; 
 var 
  i,n : Integer; 
  fb : Array [0..20] of Integer; 
 begin 
  ClrScr; 
  WriteLn ('Serie de Fibonacci de 1 a 20'); 
  WriteLn; 
  // Definicao 
  fb[0] := 0; 
  fb[1] := 1; 
  // Calculo 
  for i := 2 to 20 do 
   fb[i] := fb[i-1]+fb[i-2]; 
  // Resultados 
  for i := 0 to 20 do 
   WriteLn ('f(',i:2,')=', fb[i]:7); 
  ReadLn; // Pausa 
 End.

Código em C

// Inclui o arquivo <"stdio.h">
// stdio.h é responsável pelas funções de entrada e saída.
#include "stdio.h"

// A função main() é obrigatória em todo programa C.
void main()
{
  // Declaração de variáveis.
  int a, b, auxiliar, i, n;

  // Aqui foi necessário atribuir valores as variáveis a e b.
  a = 0;
  b = 1;

  // A função printf() escreve na tela.
  printf("Digite um número: ");
  // A função scanf obtém um valor digitado.
  scanf("%d", &n);
  printf("Série de Fibonacci:\n");
  printf("%d\n", b);

  // Com a estrutura de controle for() gero a sequência.
  for(i = 0; i < n; i++)
  {
    auxiliar = a + b;
    a = b;
    b = auxiliar;

    // Imprimo o número na tela.
    printf("%d\n", auxiliar);
  }
}

Código em Java

Os números da sequência de Fibonacci podem ser gerados por uma regra (recorrência) simples:

Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

Vejamos 4 maneiras de implementar a sequência de Fibonacci na linguagem Java. Todas as implementações criam uma classe denominada Fibonacci e um método fibo(n) do tipo long. Este método é o responsável por computar e retornar o enésimo termo da série.

IMPLEMENTAÇÃO 1 - RECURSIVA TRADICIONAL
Consiste na tradução direta da recorrência para um algoritmo recursivo. 

public class Fibonacci {

    static long fibo(int n) {
        if (n < 2) {
            return n;
        } else {
            return fibo(n - 1) + fibo(n - 2);
        }
    }

    public static void main(String[] args) {  
              
               // teste do programa. Imprime os 30 primeiros termos      
               for (int i = 0; i < 30; i++) {
            System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");
        }

    }

}
IMPLEMENTAÇÃO 2 - RECURSIVA UTILIZANDO O OPERADOR TERNÁRIO
Com o uso do operador ternário do Java é possível construir uma implementação bem mais compacta do método recursivo.

public class Fibonacci {

    static long fibo(int n) {
        return (n < 2) ? n : fibo(n - 1) + fibo(n - 2);
    }


    public static void main(String[] args) {
              
                // teste do programa. Imprime os 30 primeiros termos
        for (int i = 0; i < 30; i++) {
            System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");
        }

    }

}
IMPLEMENTAÇÃO 3 - ITERATIVA
Embora as duas implementações recursivas apresentadas sejam muito elegantes, as mesmas apresentam o problema de apresentar desempenho muito lento, pois as diversas chamadas recursivas fazem com que os mesmos valores sejam recalculados diversas vezes. Tente, por exemplo, rodar os programas recursivos para calcular fibo(50) e veja que o programa levará um longo tempo para apresentar a resposta. A seguir apresenta-se uma solução iterativa que computa o enésimo termo de uma maneira bem mais rápida.

public class Fibonacci {

    static long fibo(int n) {
        int F = 0;     // atual
        int ant = 0;   // anterior

        for (int i = 1; i <= n; i++) {

            if (i == 1) {
                F = 1;
                ant = 0;
            } else {
                F += ant;
                ant = F - ant;
            }

        }

        return F;
    }

    public static void main(String[] args) {

               // teste do programa. Imprime os 30 primeiros termos
        for (int i = 0; i < 30; i++) {
            System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");
        }

    }

}
IMPLEMENTAÇÃO 4 - RECURSIVA COM VETOR
Por fim, é apresentada uma implementação recursiva que consegue o mesmo desempenho da iterativa. O "truque" consiste em utilizar um vetor que armazena termos já calculados (ou seja, nesta solução recursiva nenhum termo é recalculado). Veja que a solução ficou mais complicada - foi necessário criar mais métodos e variáveis auxiliares.

public class Fibonacci {   

    private static int[] vetAux = new int[50];
    private static int k;

    public static long fibo(int n) {     
             k = 1; // inicializa k
             return recursao(n);
           }

    private static long recursao(int n) {
            if (n < 0) {
               return vetAux[0]; 
          } else {
           if (k < 3) {
              vetAux[n] = k - 1;
              k++;
           } else {
                 vetAux[n] = vetAux[n + 1] + vetAux[n + 2];
                 }
              return recursao(n - 1);
           }
    }
   
    public static void main(String[] args) {  // teste do programa. Imprime os 30 primeiros termos
    for (int i = 0; i < 30; i++) {
        System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");
                }
            }
        }




Comentários

Postagens mais visitadas deste blog

O QUE É BROADCASTING?

Códigos Prontos em Pascal

Desativar tecla F5 e CRTL+R utilizando JavaScript