En esta entrada vamos a ver un sencillo algoritmo para el cálculo del máximo común divisor de dos números dados. Recordemos
que el máximo común divisor de dos números enteros positivos a y
b, escrito como MCD(a, b), es el mayor de los divisores comunes de a
y de b, es decir, el mayor de aquellos números que dividen a la vez
a ambos. Por ejemplo MCD(6, 4) = 2, MCD(9, 6) = 3, y MCD(11, 9) = 1.
El cálculo del máximo común divisor resulta muy útil a la hora de
simplificar facciones, por ejemplo la fracción 60/18 podríamos
simplificarla como 60/18 = (6*10) / (6*3) = 10 / 3.
En el siguiente algoritmo podemos encontrar un método para el
cálculo del máximo común divisor. El algoritmo recibe como
parámetros de entrada dos números, a y b, y como resultado nos
muestra en pantalla el MCD(a, b). Para ello, el algoritmo se basa en
un procedimiento muy simple: primero calcula cual es el menor de los
números a y b, a continuación recorre todos los números que van
desde 1 hasta el menor de a y b, y para cada uno de ellos comprueba
si divide a la vez a ambos, utilizando la ya conocida función
módulo(), que recordemos nos devuelve el resto de la división
entera entre dos números x e y. Al final del bucle
repetir,
tendremos en la variable mcd el mayor de los números que han
dividido a la vez a a y b, es decir, su máximo común divisor.
leer(a) leer(b) min := mínimo(a, b); repetir desde x := 1 hasta x := min si (módulo(a, x) = 0) y (módulo(b, x) = 0) entonces mcd := x fin si fin repetir escribir(mcd)
Existen muchas formas de
mejorar el algoritmo anterior. Por ejemplo, no haría falta comprobar
cuales son los divisores de a y b desde 1 hasta mínimo de a y b,
bastaría con comprobar desde 1 hasta la raiz cuadrada del mínimo
(¿podría explicar el lector por qué?). Otra manera
más refinada de calcular el MCD sería mediante la factorización de
los números a y b, aunque este procedimiento no es necesariamente
más eficiente.
En la siguiente entrada de este blog veremos una forma muy sencilla, y muy eficiente, de calcular el máximo común divisor de dos números, el conocido como Algoritmo de Euclides.
No hay comentarios:
Publicar un comentario