Seqüência de Fibonacci

O matemático Leonardo Pisa, conhecido como Fibonacci, propôs no século XIII, a seqüência numérica abaixo:


(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …)
Essa seqüê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.
Desde o século XIII, muitos matemáticos, além do próprio Fibonacci, dedicaram-se ao estudo da seqüência que foi proposta, e foram encontradas inúmeras aplicações para ela no desenvolvimento de modelos explicativos de fenômenos naturais.




Uma das seqüencias recursivas mais famosas é, certamente, a Sucessão de Fibonacci, definida assim:

F(1)=F(2)=1,
F(n+2)=F(n+1)+F(n) para n>0.

Isto já nos da um programinha recursivo:

No arquivo recursivo_fibonacci.c:


#include

int fibonacci_recursivo(int n){

int fib;/*para guardar os números de Fibonacci*/

if(n==1){
fib=1;
}
else{
if (n==2){
fib=1;
}
else{
fib=fibonacci(n-1)+fibonacci(n-2);
}
}
return fib;
}

int main(void){

printf("Digite o número!");
scanf("%d",n);
printf("fibonacci(%d)=%d",n,fibonacci_recursivo(n))

return 0;
}
Agora vamos construir uma versão não-recursiva. Primeiro, como fazer isso? Vamos pensar. Quando estamos fazendo as contas na mão, seguimos este procedimento para calcular F(10):


F(1)=1
F(2)=1
F(3)=F(2)+F(1)=1+1=2
F(4)=F(3)+F(2)=2+1=3
F(5)=F(4)+F(3)=3+2=5
F(6)=F(5)+F(4)=5+3=8
F(7)=F(6)+F(5)=8+5=13
F(8)=F(7)+F(6)=13+8=21
F(9)=F(8)+F(7)=21+13=34
F(10)=F(9)+F(8)=34+21=55


Que idéia estamos usando? Simples: a cada momento, pegamos os dois valores anteriores e somamos (sem nem se preocupar com as contas anteriores!). Em um computador, podemos pensar assim: reservar três variáveis (digamos, baixo_f, alto_f e fib) e a cada momento somar as duas primeiras e jogar na terceira, sem esquecer de gravar as duas posições anteriores! Parece meio complicado, não? Então, vamos implementar a coisa para ver como funciona!


No arquivo iterativo_fibonacci.c
#include

int fibonacci_iterativo(int n){

int baixo_f=0,alto_f=0,fib=1;

for(i=1;i<=n;i++){ baixo_f=alto_f; alto_f=fib; fib=baixo_f+alto_f; } return fib; } int main(void){ printf("Digite o número!"); scanf("%d",n); printf("fibonacci(%d)=%d",n,fibonacci_iterativo(n)) return 0; }


Observe que a versão interativa perde um pouco da clareza, comparado com a versão recursiva, mas a rapidez compensa algumas dessas perdas