Scripts interessantes em C

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.

Compartilhe o link desse texto, mas se for copiar algum trecho, cite a fonte. Valorize nosso trabalho.
Mais informações na licença de uso do site.

Um Pingback/Trackback