Seguem dois scripts interessantes que fiz em C quando eu estava começando a aprender a programar. Como geralmente as pessoas começam a programar nessa linguagem, esses são exercícios muito comuns de se fazer para treino – veja mais sobre linguagem C clicando no link.
Busca binária
A pesquisa binária é um algoritmo de busca em vetores que segue o paradigma de “divisão e conquista”. Ou seja, considerando que o vetor de informações esteja ordenado, são realizadas sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso; caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na posterior metade do vetor, e se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
/*Busca binaria*/
#include <stdio.h>
#define MAX 100
int main (){
int x=0, n=0, v[MAX], i=0, meio=0, fim=0, inicio=0, resposta=0;
/* zerar o vetor */
for(i=0; i<100; i++){
v[i]=0;
}
/* entrada de dados */
printf("Diga qtos numero tera sua sequencia: ");
scanf("%d", &n);
printf("Digite uma sequencia em ordem crescente: ");
for(i=0;i<n;i++){
scanf("%d", &v[i]);
}
printf("Digite o numero a ser procurado: ");
scanf("%d", &x);
/* busca binaria */
fim=n-1;
while(inicio<=fim){
meio=(inicio+fim)/2;
if(v[meio]==x)
return meio;
if(v[meio]<x) inicio=meio+1; /* elimina termos antes do meio, jah q valor eh maior q o valor do meio */ if(v[meio]>x)
inicio=meio-1; /* elimina termos depois do meio, jah q valor eh menor q o valor do meio */
}
return(-1);
}
Esse algoritmo é muito mais rápido que a busca sequencial, sendo análogo ao método utilizado ao buscar alguma informação em uma lista telefônica ou um capítulo de livro sem índice.
Verificação de CPF
O Cadastro de Pessoas Físicas (CPF ou CPF-MF) é o registro mantido pela Receita Federal do Brasil no qual podem se inscrever, uma única vez, quaisquer pessoas naturais, independentemente de idade ou nacionalidade, inclusive falecidas. Cada inscrito é unicamente identificado por um número de inscrição no CPF de 11 dígitos decimais, sendo os oito primeiros aleatoriamente designados no momento da inscrição. Já o nono (penúltimo) dígito indica a região fiscal responsável pela inscrição. Por fim, o décimo e o décimo-primeiro são dígitos verificadores calculados de acordo com o algoritmo descrito nesse artigo.
Dígito verificador (ou algarismo de controle) é um mecanismo de autenticação utilizado para verificar a validade e a autenticidade de um valor numérico, evitando fraudes ou erros de transmissão/digitação. Consiste em um ou mais algarismos acrescentados ao valor original e calculados a partir deste através de um determinado algoritmo.
Essa rotina em C calcula os dois dígitos verificadores do CPF e retorna se o CPF é válido ou não. Nesse caso, o método de cálculo desses dígitos se baseia em uma rotina tradicional, a “Módulo 11”. Para calcular o primeiro dígito verificador, cada dígito do número, começando da direita para a esquerda (do dígito menos significativo para o dígito mais significativo) é multiplicado, na ordem, por 2, depois 3, depois 4 e assim sucessivamente, até o primeiro dígito do número. O somatório dessas multiplicações dividido por 11. O resto desta divisão (módulo 11) é subtraido da base (11); o resultado é o dígito verificador. Para calcular o próximo dígito, considera-se o dígito anterior como parte do número e efetua-se o mesmo processo.
/*Verificação de CPF - cálculo do dígito verificador*/
#include <stdio.h>
#define MAX 20
int main (){
int cpf[MAX], i=0, n=11, interno[MAX], soma=0, resto=0, digito=0, digitoverificador;
/* zerar o vetor */
for(i=0; i<11; i++){
interno[i]=0;
}
for(i=0; i<11; i++){
cpf[i]=0;
}
/* entrada de dados */
printf("Digite o numero do CPF, sem pontos ou tracos: ");
for(i=0;i<11;i++){
scanf("%d", &cpf[i]);
}
/* calculo do primeiro digito verificador */
for(i=0;i<9;i++){
n=n-1;
interno[i]=n*cpf[i];
}
for(i=0;i<9;i++){
soma+=interno[i];
}
resto=soma%11;
digito=11-resto;
if(resto<2)
digitoverificador=0;
else
digitoverificador=digito;
if(digitoverificador!=cpf[9]){
printf("\n * CPF invalido *");
}
/* calculo do segundo digito verificador */
n=12;
for(i=0;i<9;i++){
n=n-1;
interno[i]=n*cpf[i];
}
for(i=0;i<9;i++){
soma+=interno[i];
}
resto=soma%11;
digito=11-resto;
if(resto<2)
digitoverificador=0;
else
digitoverificador=digito;
if(digitoverificador!=cpf[10]){
printf("\n * CPF invalido **");
}
else
printf("\n * CPF valido *");
return(0);
}
O CPF utiliza o módulo 11 duas vezes seguidas, obtendo dois dígitos verificadores.
Qualquer melhoramento/correção/comentário será bem-vindo.
One comment