Cargando...
 
Imprimir

Algoritmo de Euclides

El algoritmo de Euclides sirve para obtener el máximo común divisor (abreviado normalmente como M.C.D.) de dos números enteros positivos. El mínimo común múltiplo (M.C.M.), puede obtenerse también con éste algoritmo, haciendo una sencilla operación con el M.C.D. obtenido.

Se llama así por Euclides de Alejandría(external link), un matemático griego que vivió en los tiempos del faraón Ptolomeo I, del que nos han quedado algunos textos recopilatorios del saber matemático y geométrico de su época. No es que Euclides escribiera tal cual éste algoritmo, sino que, aparentemente, dejó escritas algunas relaciones entre números que son la base de lo que hoy llamamos MCD.

Es uno de los algoritmos típicos que los profesores de programación ponen a sus alumnos para practicar el bucle repetir-mientras o hacer-hasta (repeat-until o do-while) pasando valores de una iteración a otra del bucle.

Máximo Común Divisor (MCD)

El máximo común divisor de dos números enteros positivos a y b es otro número entero positivo c tal que si dividimos a/c y b/c, los restos de las divisiones son 0, y además no existe otro número mayor que c que tenga esta caracterísitica. Como nos decían en el "cole", el máximo común dívisor (mcd) de dos enteros a y b es el mayor entero c que divide exactamente a a y b.

Aunque en el colegio nos enseñan a encontrar el mcd a partir de la descomposición en factores primos de a y b, esa no es una buena forma de obtener el mcd computacionalmente, ya que el algoritmo para descomponer en factores primos es muy costoso, en términos de computación. El algoritmo de Euclides es bastante más eficiente para obtener el mcd, aunque normalmente sorprende un poco cuando tenemos contacto con él por primera vez.

El algoritmo de Euclides es el siguiente:

Algoritmo de Euclides
Siendo a y b dos enteros positivos tales que a>b, comenzamos dividiendo a/b, con lo que obtendremos un resto r1 y un cociente q1. Hacemos la operación q1=a/b, utilizando la división entera, sin decimales.... pero realmente no sólo nos interesa el resultado o cociente de la división, sino que nos interesa también el resto, así que la operación la vamos a reescribir de otra forma.

Es importante que llamemos "a" al mayor de los dos números (siempre el mayor va a ser a). Debemos dividir a entre b y obtener un cociente (al que llamaremos q1) y un resto (al que llamaremos r1).

Obtenidos ese cociente y ese resto, se cumple que:

a=q1·b+r1


Los lenguajes de programación suelen tener un operador para efectuar la división entera (con lo que obtendremos q1. Por ejemplo, en C#: "q1=a/b;"), y otro para obtener el resto o módulo de la división (con lo que obtendremos r1. Por ejemplo, en C#: "r1=a%b;").


A partir de esa primera división, es necesario repetir un proceso:

  • dividir el dividendo del paso anterior entre el resto del paso anterior
  • despreciar el cociente
  • si el resto es 0, el mcd es el divisor de esta operacion, es decir, el último resto no nulo (recordemos que el divisor de esta operación fué el resto en la anterior.
  • Si el resto no es 0, ir al primer paso

Es un poco engorroso la primera vez, pero realmente es un algoritmo muy sencillo.

Siguiendo con el ejemplo, en la segunda iteración, dividiríamos b/r1 obteniendo un resto r2 (hacemos la operación de división para obtener el cociente, al que llamamos q2 y la de obtener el resto, al que llamamos r2), de tal manera que se cumpliría lo siguiente:

b=q2·r1+r2


En la tercera iteración, dividimos r1/r2 obteniendo un resto r3

r1=q3·r2+r3


Y se continúa así hasta obtener un resto 0. El último resto (llamémosle rk) distinto de cero es el mcd.

rk-2=qk·rk-1+rk

rk-1=qk+1·rk+0



rk es el mcd(a,b)

Es decir, empezamos dividiendo un número entre otro (obteniendo el resto también, no sólo el cociente), y a partir de ahí, seguimos dividiendo el número más pequeño entre el resto que nos ha salido... y continuamos dividiendo por el resto anterior una vez y otra hasta que en ese proceso repetitivo obtengamos un resto que sea 0. ¡Ya lo tenemos!. El mcd es es resto anterior (que no es cero).

Como comentábamos al principio, es muy sencillo implementarlo iterativamente. Basta tener en cuenta que en cada vuelta del bucle, y siempre a partir de la segunda iteración hay que hacer que el divisor sea el resto de la iteración anterior y el dividendo sea el divisor de la iteración anterior.

Vamos a hablar de código utilizando C#.

En el código que construiremos vamos a utilizar dos variables enteras i1 e i2, que inicialmente van a contener los valores de los dos enteros a y b que se pasen como parámetros, de tal manera que i1 tendrá al mayor de los dos, e i2 al más pequeño... y a partir de ahí nos metemos en un bucle. La dinámica es siempre la misma: obtenemos el resto de la división, y si no es 0, debemos hacer otra repetición. Pero antes de la siguiente repetición, desplazamos los valores: lo que contenía i1 ya no nos sirve. Metemos en i1 lo que tiene i2, y en i2 el resto que hemos obtenido....

El algoritmo de euclides en C#
static int EuclidesMCD(int a, int b) {
   int iaux; //auxiliar
   a = Math.Abs(a); //tomamos valor absoluto
   b = Math.Abs(b);
   int i1=Math.Max(a,b); //i1 = el más grande
   int i2=Math.Min(a,b); //i2 = el más pequeño
   do
   {
      iaux = i2;  //guardar divisor
      i2 = i1 % i2; //resto pasa a divisor
      i1 = iaux;  //divisor pasa a dividendo
   } while (i2 != 0);
   return i1; //ultimo resto no nulo
}


Al principio cuesta un poco de coger... te recomiendo hacer una traza mentalmente (o mejor, ayudándote de papel).

Te darás cuenta de cómo se van "desplazando los valores" a medida que vamos dividiendo hasta obtener el resto 0... aunque, realmente... no estamos utilizando los cocientes, sino sólo los restos ;-)

Aunque en la introducción hemos mencionado la división ("/"), realmente no es del todo cierto... sólo queremos los restos, no el cociente...(operador módulo o resto: "%" en C#). Hemos introducido esta pequeña mentira en la explicación (pero no en el código) porque cuando dividimos "a mano", realmente en la misma operación de división obtenemos dos resultados a la vez: por un lado el cociente y por otro, el resto. Sin embargo, los lenguajes de programación hacen cada una de esas cosas por separado: pueden obtener un cociente sin necesidad de obtener un resto y al revés, obtener un resto sin necesidad de dividir... así que en nuestro algoritmo no dividimos realmente: sólo obtenemos el resto. Si lo hiciéramos "a mano", tendríamos que dividir, con lo que obtendríamos el cociente y el resto simultáneamente, pero despreciaríamos el cociente y nos quedaríamos sólo con el resto.

Mínimo Común Múltiplo. (MCM)


Muy relacionado con el máximo común divisor está el mínimo común múltiplo (mcm).

El mcm de dos enteros positivos a y b es un valor c entero y positivo tal que al dividir c/a y c/b el resto es 0, y además no existe otro número menor que c que cumpla esta condición.

Hay una relación muy sencilla entre mcm y mcd. Es ésta:

mcm(a,b)=(a·b)/mcd(a,b)


Así pues, también podemos obtener el mcm mediante el algoritmo de Euclides.

Obtener el MCM con el algoritmo de Euclides, en C#
static int EuclidesMCM(int a, int b)
{
    return (a / EuclidesMCD(a, b)) * b;
}

NOTA
Observa que primero se divide a entre el mcd, en lugar de multiplicar a*b. Esto se hace para evitar un posible desbordamiento al multiplicar a*b.


Ultima edición por vic .
Página última modificacion en Miércoles 25 de Julio, 2012 22:20:54 CEST.



¿Dónde estoy?

Estás en La tecla de ESCAPE, un sitio web personal en el que nos gusta hablar de algoritmos, metodología de la programación, personajes de informática, tecnología, ingeniería del software, internet, y cualquier otra tontería que se nos ocurra.
Leer más / Términos de uso (ToS)

Este sitio web usa cookies para su funcionamiento. Navegar por éste sitio supone la aceptación de la política de cookies -
Política de cookies +