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)
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");
}
}
}
Leia mais
em: Sequência de
Fibonacci em Java http://www.devmedia.com.br/sequencia-de-fibonacci-em-java/23620#ixzz30n9YwWWZ
