Sequência de Fibonacci e Algoritmos

Fala, galera!

Sem blá, blá, blá vamos direto ao cerne da questão, como aplicar a lógica de Fibonacci em algoritmos, mas antes é importante entendermos a matemática da coisa.

Com base num artigo de Matemática Didática sabemos que:

F(n)=((1+5^(1/2))/2)^n/5^(1/2)

Legal né?!  :P

Sei que pode parecer tão símples quanto mandarim, mas se tratando de matemática  e algoritmos é importantíssimo sabermos escrever formulas matemáticas como apresentado acima, pois é praticamente dessa forma que se aplica num código computacional.

Mas não se preocupe, sei que imagens são mais amigáveis, portanto segue a mesma formula numa representação mais “humana”:

Lembrando que:

Então, se pegarmos um número qualquer, por exemplo o 4, teremos:

Ou seja, o numero Fibonacci equivalente a 4 é o 3 :)

Agora que já entendemos, aprendemos como se calcula um número Fibonacci equivalente vamos as desafio!

Fibonacci e Algoritmos \o/

Importante: quando usamos uma linguagem algorítmica  como o Portugol não temos função de arredondamento, e levando em conta que os números obtidos pela formula acima são fracionados, é preciso que trabalhemos com aproximação. Então bora lá:

algoritmo queridoFibonacci
   variaveis
      f: real
      n: inteiro

   inicio
      para n de 0 ate 10 faca
         f = exp((1 + raizq(5)) / 2, n) / raizq(5)
         escreva( "O número Phi de ", n ,"é ", f )
     fimpara
  fimalgoritmo

Observe que na linha 7 criamos um laço para que iniciará em 0 e terminará em 10 percorrendo número por número onde o número é n.

Na linha 8 é que a salada acontece. Calcula-se a exponenciação da raiz quadrada de 5 mais 1 dividido por 2 cujo o resultado é elevado a n (expoente). O resultado a exponenciação é dividido pela raiz quadrada de 5 e armazenado em f. uffa!

Na linha 9 exibimos o resultado em tela.

Veja mais sobre operadores aritméticos em Portugol clicando aqui.

Em PHP já conseguiríamos trabalhar com o arredondamento, e ficaria assim:

for ( $n = 0; $n < 10; $n++ ) {
   $f = pow((1 + sqrt(5)) / 2, $n) / sqrt(5);
   echo ' [' . round( $f ) . '] ';
}

Bom, mas se meu professor pedir que seja feito com comandos de desvios condicionais se e senao?
Sem crise! Vamos analisar a lógica da coisa:

Observe que a partir da terceira sequência Fibonacci  é a soma do último com o penúltimo. Certo?

Então poderíamos dizer que F3 = F1 + F2.

Vamos pensar de forma lógica com Portugol

Precisamos ter em mente que nosso código terá a missão de escrever na tela uma sequência de números em que cada número é a soma de sua última com a penúltima recorrência.

algoritmo Fibonacci
   variaveis
      fib, aux1, aux2, n : inteiro

   inicio
      fib <- 0
      aux1 <- 1
      aux2 <- 1

      para n de 0 ate 10 faca
         se n < 2 entao
            fib <- aux1
         senao
            fib <- aux1 + aux2
            aux1 <- aux2
            aux2 <- fib
         fimse
            escreval( fib );
      fimpara
   fimalgoritmo

Agora para fazer esse mesmo algoritmo em PHP basta transcrevermos para a linguagem:

$fib = 0;
$aux1 = 1;
$aux2 = 1;

for( $n = 0; $n < 10; $n++ ) {
   if( $n < 2 ) {
      $fib = $aux1;
   } else {
      $fib = $aux1 + $aux2;
      $aux1 = $aux2;
      $aux2 = $fib;
   }

      echo $fib . '<br />';
}

Observe que a partir da terceira vez que o laço for passa, na linha 9, a variável $fib recebe a soma das variáveis $aux1 e $aux2 onde $aux2 recebe o último resultado de $fib e $aux1 recebe o valor de $aux2.

Confesso que eu também achei bem complicado, mas foi exatamente por causa disso (e uma nota baixa que tirei na prova de algoritmos :P ) que resolvi fazer esse artigo. Espero ter ajudado ;)

Deixe uma resposta

O seu endereço de email não será publicado Campos obrigatórios são marcados *

*

Você pode usar estas tags e atributos de HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>