ALGORITMO DE EUCLIDE (GRUPO 10)

Ø ,ALGORITMO DE EUCLIDES:

Un algoritmo es una secuencia de pasos para conseguir un resultado.

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD) entre dos números enteros. Fue originalmente descrito por Euclides en la proposición 2 del libro VII de su libro Elementos. Tiene numerosas aplicaciones en teoría de números y ciencias de la computación.

Ø PASOS DEL ALGORITMO DE EUCLIDES:

El algoritmo de Euclides es un procedimiento para calcular el m.c.d. de dos números. Los pasos son:

1 Se divide el número mayor entre el menor.

2 Si:

a- La división es exacta, el divisor es el m.c.d.

b- La división no es exacta, dividimos el divisor entre el resto obtenido y se continúa de esta forma hasta obtener una división exacta, siendo el último divisor el m.c.d.

Ejemplo: 

m.c.d. (72, 16) = 8

    Al dividir a entre b (números enteros), se obtiene un cociente q y un residuo r. Es posible demostrar que el máximo común divisor de a y b es el mismo que el de b y r. Este es el fundamento principal del algoritmo.

De acuerdo con este fundamento, para calcular el máximo común divisor de a y b tan sólo es necesario calcular el máximo común divisor de b y r. Como b y r son números más pequeños, el número de operaciones se reduce. Además, para calcular el máximo común divisor de b y r se puede aplicar la misma regla recurrentemente.

Ejemplo 1:

Por ejemplo, para calcular el máximo común divisor de 2366 y 273 se podría utilizar la siguiente secuencia de operaciones:

2366 entre 273 es 8 y sobran 182

273 entre 182 es 1 y sobran 91

182 entre 91 es 2 y sobra 0

Esta secuencia de operaciones se puede interpretar con el siguiente significado:

Mcd (2366,273) =  mcd (273,182)

Mcd (273,182) = mcd (182,91)

Mcd (182,91) = mcd (91,0)

De esta manera se concluye que el máximo común divisor de 2366 y 273 es 91 (porque mcd (91,0).

Ejemplo 2:

A = 246                B = 118

a =  246   = 2 + 10                   q1 = 2            r1 = 10

b     118            118  

b =  118   = 11 + 8                    q2 = 11            r2 = 8

r1     10              10  

r1 =  10   = 1 + 2                       q3 = 1            r3 = 2

r2       8            8  

r2 =  8   = 4 + 0                         q4 = 4           r4 = 0

r3     2    

m.c.d (246, 118)           

Ejemplo:

Para hallar el residuo de una división utilizamos mod, así con (A mod2=0) podemos saber si A es un numero par o impar.
Para resolver el problema tengo que dividir un numero por otro más pequeño, si el residuo es 0 es su mcd, si no dividimos el divisor entre el resto. Bien ¿puedo almacenar el resultado en una variable para así poder realizar la siguiente división entre el cociente y el resto? Es decir:

—  resultado = a/b
resto = (a mod b)

¿Así con la variable resto puedo realizar el bucle mientras ésta no sea 0?

mientras resto<>0 hacer