quarta-feira, 25 de novembro de 2009

Um passo de cada vez... Algoritmos (fatorial/fibonacci)

Apesar do título do post ser um passo de cada vez, hoje veremos 2 algoritmos clássicos: Fatorial e Números de Fibonacci.
A razão para vermos os 2 ficará clara mais adiante em nossos estudos. Sem mais conversa vamos a eles.

Fatorial
Se você não sabe do que se trata, veja aqui.
Um exemplo de código que calcula o fatorial de um número em C, pode ser visto abaixo.


//PROGRAMA PARA CALCULAR A FATORIAL DE UM NUMERO DIGITADO
#include <stdio.h>
#include <stdlib.h>
 
int main(){
 int cont = 1, num, fatorial = 1;
 printf("Digite um numero inteiro:\n");
 scanf("%d",&num);
 while (cont <= num){
    fatorial *= cont;
    cont++;
 }
 printf("O fatorial de %d e %d\n",num,fatorial);
 system("pause");
}


Definimos e inicializamos uma variável inteira que chamamos de fatorial. Na linha 10, armazenamos nela o seu valor anterior multiplicado pelo valor da variável inteira contador, que teve o seu valor inicial definido como 1 (um), e é incrementado a cada repetição até alcançar o valor digitado pelo usuário.
Se o usuário digitar o número 4, por exemplo, haverá 4 repetições do bloco de comandos controlado pelo while, que resultará em:
 1 * 2 * 3 * 4
O resultado desta operação será o valor 24, que o fatorial do número 4.
Simples assim ;).

Sequência de Fibonacci
Antes de olhar o código, dê uma olhada aqui.
Agora que você já sabe o que é (sabe mesmo?), vamos a um exemplo em C.


//PROGRAMA QUE IMPRIMA OS N PRIMEIROS TERMOS
//DA SEQUENCIA DE FIBONACCI.
#include <stdio.h>
#include <stdlib.h>
 
int main(){
  int i, termos, termo, par = 1, impar = 1;
 
 printf("Digite o numero de termos desejado:\ ");
 scanf("%d",&termos);
 printf("\n");
 if (termos > 0){
    printf("0");
    i = 1;
    while (i<termos){
       if (i<3)
          printf(",1");
       else{
          termo = par + impar;
          printf(",%d",termo);
          if (i%2 == 0)
             par = termo;
          else
             impar = termo;
       }
       i++;
    }
 }
 else
    printf("NUMERO INVALIDO!!!\n");
 printf(".\n");
 system("pause");
}


Não sei se você reparou, mas observando a sequência de Fibonacci podemos ver que os termos de ordem par são a soma do termo ímpar e do termo par imediatamente anteriores a ele, exceto para os 2 primeiros termos, que por definição são 0 e 1.
Observe a figura abaixo.



Partindo desta observação, definimos duas variáveis inteiras chamadas de par e ímpar para armazenar os termos par e ímpar atuais, e assim, executar a soma dos mesmos para obter o próximo termo. Se este próximo termo for par, armazenamos ele em par, se for ímpar, em ímpar (acredito que isto seja lógico ;).
O if da linha 16 é para garantir que os 2 primeiros termos sejam 0 e 1, atendendo a definição.

Alguma dúvida? Pode perguntar nos comentários.
Por hoje é só. Até a próxima.

Um comentário:

  1. a sequência de Fibonacci não tem o número zero.

    ResponderExcluir