Hace ya varios días estuvimos revisando el Algoritmo para Hallar el Máximo Común Divisor, que para ser más exactos recordemos que era el algoritmo de Euclides; y acudimos precisamente a este algoritmo debido a su facilidad para implementarlo en prácticamente cualquier lenguaje de programación.
Y bueno, te preguntarás el por qué estoy mencionando ese algoritmo en esta entrada, y la razón es porque el Máximo Común Divisor está muy relacionado con el Mínimo Común Múltiplo, la cual ya la comentaremos en unos instantes, pero primero veamos en sí que es el M.C.M.
El Mínimo Común Múltiplo de dos números 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.
Ahora sí, veamos cual es la relación que existe entre el mcm y el mcd:
mcm(a,b) = (a*b) / mcd(a,b)
Sin embargo, para evitar un posible desbordamiento al multiplicar a*b, podemos reorganizar la ecuación de tal forma que primero se realice la división entre a y el mcd(a,b) y posteriormente se realice la multiplicación por b, quedando entonces de la siguiente forma:
mcm(a,b) = (a / mcd(a,b)) * b
La verdad, creo que este algoritmo no tiene ningún inconveniente para ser implementado en los lenguajes que hemos estudiado el MCD, ya que bastaría solamente con insertar el algoritmo que vimos del mcd dentro de un método que retorne su valor y posteriormente calcular el mcm.
Sin embargo, existe otra forma, la cual también ha sido deducida de los algoritmos de Euclides mediante la cual podremos calcular el MCM sin necesidad de calcular el MCD, aunque esta forma puede que no sea muy eficiente principalmente cuando se realiza el proceso con números muy grandes.
Pues bien, la descripción de este algoritmo sería la siguiente considerando que los dos números son enteros positivos:
1. Seleccionamos el menor de los dos números a y b
2. Realizamos un ciclo que va desde un valor i = 1 hasta i = min(a,b)
3. Dentro del ciclo realizamos una condición, en la cual vamos verificando si el resto de la división de a y b entre cada uno de los valores que toma i dentro del ciclo. De ser los dos restos iguales a 0, hacemos los siguientes pasos:
4. Seleccionamos ese valor i = mcd(a,b)
5. Por lo tanto, el mcm sería entonces: mcm(a,b) = (a / mcd(a,b)) * b
Si te fijas bien, ésta es una variante al algoritmo de Euclides, pues a diferencia del método que vimos en esta entrada en el cual se realiza un proceso iterativo a través de divisiones, lo cual nos llevará al resultado de forma más rápida al ser menos la cantidad de iteraciones que se llevan a cabo.
Mientras que en el algoritmo que acabamos de ver, el ciclo se debe realizar una cantidad de veces igual al valor menor entre a y b, haciendo más lento el proceso.
Un ejemplo claro de esta situación lo podemos ver si analizamos el proceso con los números 9876 y 3321. Si lo hacemos por el método de hallar el resto de la división, la cantidad de iteraciones serían 6; veámoslo:
2. 3321 % 3234 = 87
3. 3234 % 87 = 15
4. 87 % 15 = 12
5. 15 % 12 = 3
6. 12 % 3 = 0
Cabe aclarar que lo acabamos de calcular fueron solamente los restos y no los cocientes de cada división (para entender mejor este proceso, revisa este artículo). Como lo explicamos en aquella entrada, el MCD es entonces el último resto diferente de 0, es decir, el resto que calculamos en la penúltima iteración.
Sin embargo, si lo hacemos de la otra forma, la cantidad de iteraciones serían 3321, ya que el ciclo debe repetirse una cantidad de veces igual al menor valor entre a y b.
Bueno, por ahora esto es todo, sin embargo a continuación podrás ver como podemos implementar estas dos formas en varios lenguajes de programación y cómo se vería representado a través de un diagrama de flujo:
 |
Pseudocódigo |
 |
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