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 colegio, 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 hablando en términos de computación.
Sin embargo, Euclides quien fue un matemático griego que vivió en los tiempos del faraón Ptolomeo I, planteó un algoritmo bastante más eficiente para obtener el MCD, aunque la verdad puede parecer un poco complicado 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:
Los lenguajes de programación suelen tener formas u operadores para efectuar la división entera con lo que obtendremos q1 (por ejemplo, en Java: "q1=(int) a/b;"), y otro para obtener el resto o módulo de la división, con lo que obtendremos r1 (por ejemplo, en Java: "r1=a%b").
A partir de esa primera división, es necesario repetir un proceso:
- Dividir el divisor 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 fue el resto en la anterior.
- Si el resto no es 0, ir al primer paso
Puede que este proceso parezca un poco engorroso la primera vez, pero en realidad es un algoritmo muy sencillo de aplicar.
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:
En la tercera iteración, dividimos r1/r2 obteniendo un resto r3:
Y se continúa así sucesivamente hasta obtener un resto 0. El último resto (al que podemos llamarlo rn) distinto de cero es el mcd.
El máximo común divisor entre a y b es entonces rn.
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 entonces el 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.
Bien, debido a que este es un proceso iterativo, es algo sencillo de implementar en los diversos lenguajes de programación, pero para no hacer este artículo más largo, mostraré el código fuente en Lenguajes como Java, C# y Python en otras entradas:
a=q1*b+r1
Los lenguajes de programación suelen tener formas u operadores para efectuar la división entera con lo que obtendremos q1 (por ejemplo, en Java: "q1=(int) a/b;"), y otro para obtener el resto o módulo de la división, con lo que obtendremos r1 (por ejemplo, en Java: "r1=a%b").
A partir de esa primera división, es necesario repetir un proceso:
- Dividir el divisor 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 fue el resto en la anterior.
- Si el resto no es 0, ir al primer paso
Puede que este proceso parezca un poco engorroso la primera vez, pero en realidad es un algoritmo muy sencillo de aplicar.
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í sucesivamente hasta obtener un resto 0. El último resto (al que podemos llamarlo rn) distinto de cero es el mcd.
rn-2=qn*rn-1+rn
rn-1=qn+1*rn+0
El máximo común divisor entre a y b es entonces rn.
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 entonces el 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.
Bien, debido a que este es un proceso iterativo, es algo sencillo de implementar en los diversos lenguajes de programación, pero para no hacer este artículo más largo, mostraré el código fuente en Lenguajes como Java, C# y Python en otras entradas:
 |
Pseudocódigo y Diagrama de Flujo |
 |
Código Fuente en Java |
 |
Código Fuente en C |
 |
Código Fuente en C++ |
 |
Código Fuente en C# |
 |
Código Fuente en Python |
No hay comentarios.:
Publicar un comentario