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.

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.

O CPF utiliza o módulo 11 duas vezes seguidas, obtendo dois dígitos verificadores.

Qualquer melhoramento/correção/comentário será bem-vindo.