• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

kelker

Algoritmo de Euclides

1 mensagem neste tópico

Boas.

Trago-vos mais uma curiosidade:

Algoritmo de Euclides

Este algoritmo serve para achar o máximo divisor comum entre números de um modo rápido e no mínimo curioso.

Consideremos por exemplo os números 42783 e 9857 (escolhidos aleatoriamente), qual será o máximo divisor comum entre eles, sem recorrer à factorização?

Fazemos então a igualdade: 42783 = 9857*a + b (algoritmo da divisão de 42783 por 9857), em que a e b são números naturais.

Se fizermos a divisão, obtemos a =4 e b=3355.

Começa então um procedimento iterativo:

Pegamos no 9857 e colocamo-lo no sítio do 42783, o b toma o lugar do 9857, (o a deixa de ter interesse).

Deste modo obtemos: 9857 = 3355*c + d , (c e d pertencem a IN).

Obtém-se: c = 2 e d = 3147.

De modo análogo:

3355 = 3147*1 + 208

3147 = 208*15 + 27

208 = 27*7 + 19

27 = 19*1 + 8

19 = 8*2 + 3

8 = 3*2 + 2

3 = 2*1 + 1

2 = 1*2 + 0 

O máximo divisor comum será o um neste caso (o que significa que os números em causa são primos entre si), ou seja, o máximo divisor comum aparece neste procedimento na igualdade anterior à que der resto (;) zero.

Deixo um desafio: tentem provar o porquê do método funcionar deste modo, ou seja, qual a lógica subjacente.

Nota:Uma aplicação disto, para quem não se lembre: simplificar fracções. Caso não se tenha calculadora convém saber dividir bem...

Espero que tenham gostado.

kelker

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora