Expressões Regulares

Wiki brasileiro sobre expressões regulares: http://www.regex.pro.br
 

CPF – Cálculo do Dígito Verificador

O número do CPF é composto de 11 dígitos, sendo os dois últimos os dígitos de verificação.
Para verificar a validade do número do CPF é necessário utilizar um cálculo efetuado com os 9 primeiros números que geram os 2 últimos números, que são os dígitos verificadores. Vamos tomar como exemplo o número 123.456.789-09

Calcular o 1º Dígito Verificador

Faça a soma da multiplicação dos 9 primeiros dígitos por 10, 9, 8, … , 3, 2, respectivamente:

1 * 10
2 *   9
3 *   8
4 *  7
5 *  6
6 *  5
7 *  4
8 *  3
9 *  2

Computacionalmente, a expressão é:
Soma = (1*10) + (2*9) + … + (8*3) + (9*2)

Em seguida, dividimos essa Soma por 11, porém, do resultado só utilizaremos a parte inteira, que será multiplicada por 11:

Supondo Soma = 210, se Valor = (Soma\11) * 11, então Valor = (210\11)*11, logo Valor = (19)*11, pois o operador “\” indica que a divisão efetuada gerará um quociente inteiro.

Enfim, subtraímos Valor de Soma, Resultado = Soma – Valor

Tendo o valor de Resultado, devemos fazer a seguinte verificação:

• Se Resultado for igual à 1 ou à 0, então o 1º dígito verificador é 0;
• Caso contrário, o 1º dígito verificador é o resultado da subtração de Resultado de 11.

2º Dígito Verificador

Primeiro calculamos a soma da multiplicação dos 9 primeiros dígitos por 11, 10, 9, … , 4, 3, respectivamente e em seguida somamos com (Digito1*2), sendo que Digito1 é o valor encontrado para o 1º dígito verificador. Ou seja
Soma = (1*11) + (2*10) + … + (8*4) + (9*3) + (Digito1*2)
O resto é semelhante ao que foi feito anteriormente. Dividimos e multiplicamos por 11. (Nota: Ao multiplicarmos utilizamos o valor inteiro da divisão).

Valor = (Soma/11) * 11
Por fim, subtraímos Valor de Soma.

Resultado = Soma – Valor
Agora analisamos Resultado:

• Se Resultado for igual à 1 ou à 0, então o 2º dígito verificador é 0;
• Caso contrário, o 2º dígito verificador é o resultado da subtração de Resultado de 11.

Torre de Hanói

Um quebra-cabeças interessante. Foi inventado e vendida como brinquedo, no ano de 1883, pelo matemático francês Edouard Lucas. Para dar um ar “misterioso” ao jogo, ele afirmou que o inventor do quebra-cabeças seria “Claus de Siam, professor em Li-Sou-Tsian”,  que nada mais é que um anagrama de “Lucas d´Amiens professor em Saint-Louis”…

A idéia é transferir-se os oito discos que formam a torre para um dos dois bastões vazios. Para tanto deve-se movimentar um único disco por vez, e não se pode colocar um disco maior sobre um menor. Segundo cálculos matemáticos, o menor número de movimentos necessários para a solução do problema, com uma torre de 8 círculos, é de 255 movimentos!

A formula matemática desenvolvida por Edouard Lucas para descobrir o número mínimo de movimentos para a solução do problema é: “2n-1″, tal que “n” é o número de círculos na pilha.

Na descrição original do quebra-cabeças, este seria a versão simplificada de uma torre dedicada a “Brahma”, na cidade de Benares. Esta torre porém, teria 64 discos de ouro, que necessitariam de 18.446.744.073.709.551.615 movimentos para ser mudada, respeitando-se as regras acima mencionadas. Movendo-se um disco por segundo, o tempo necessário para a solução deste problema seria contado em bilhões de anos…

Pela regra de Lucas, o número mínimo de movimentos seria 127 (é interessante notar que o acréscimo de um único disco, gera o aumento de 128 movimentos!).

Pode-se improvisar uma “Torre de Hanói”, utilizando-se, por exemplo, cartas de baralho, do Ás ao 8, marcando-se três pontos em uma folha de papel.
 
Extraído de:
http://www.jogos.antigos.nom.br/hanoi.asp

Lógica – Aula 1

Jogo Lógico:
Acesse www.somatematica.com.br >> Jogos Matemáticos >> Torre de Hanói

História da Computação:
http://www.ime.usp.br/~macmulti/historico/index.html

Listas de Execícios:
Lista 1

Bibliografia:
500 algoritmos resolvidos
ANITA LOPES  
GUTO GARCIA  
Editora Campus
Algoritmos e Estruturas de Dados  
LAGES & GUIMARAES
Editora LTC
Projeto de Algorítmos: com Implementações em Pascal e C   
NIVIO ZIVIANI & Thomson Pioneira
Editora Pioneira
Algoritmos
DIRCEU DOUGLAS SALVETTI & LISBETE MADSEN BARBOSA
Editora Makron Books
Raciocínio Lógico
JONOFON SÉRATES
Volumes 1 e 2
Editora Teixeira