El ejercicio de programación de esta semana es escribir un programa Java para calcular MCD y MCM de dos números . MCD significa Máximo factor común y MCM significa Mínimo común multiplicador, ambas son operaciones matemáticas populares y están relacionadas entre sí. El MCD es el número más grande que divide ambos números sin dejar ningún resto, por ejemplo, si dos números son 24 y 40, entonces su MCD es 8 porque 8 es el número más grande que divide perfectamente a 24 y 40, sin dejar ningún resto.
De manera similar, LCM es el número más bajo que es perfectamente divisible por los dos números, por ejemplo, si el número dado es 40 y 24, entonces su MCM es 120 porque este es el número más bajo que es perfectamente divisible por 40 y 24.
Ya que, puede calcular LCM una vez que tenga MCD porque MCM de dos números a y b no es más que a*b/GCF(a, b) . Entonces, en realidad, solo necesitamos calcular primero el máximo común divisor y luego podemos encontrar el mínimo común multiplicador.
Una de las formas más fáciles de encontrar el MCD de dos números es usando el algoritmo de Euclides. Este es un algoritmo recursivo que encuentra el MCD de dos números mediante una reducción radical del tamaño del problema al cambiar el MCD(A, B) por el MCD(B, A mod B) donde A>B. El algoritmo fue propuesto por Euclides hace unos 2250 años. Consulte Introducción a los algoritmos para obtener más información sobre el algoritmo de Euclides, una forma eficiente de encontrar el MCD de dos números.
De todos modos, funciona como a continuación:
public static int GCF( int a, int b) {
if (b = = 0) {
return a;
} else {
return (GCF(b, a % b));
}
}
Puede ver que el caso base es cuando el segundo número se convierte en cero, en ese caso, GCF no es más que el primer número; de lo contrario, sigue llamando al método GCF() usando la recursividad, pero cada vez que el segundo número se vuelve más pequeño debido al uso del operador módulo.
¿Cómo calcula el algoritmo de Euclides GCD?
El algoritmo euclidiano es fácil de entender una vez que recorre el algoritmo con un ejemplo y ve el diagrama de flujo. Calculemos el MCD de 40 y 24 usando el algoritmo euclidiano, recuerda que el primer número debe ser mayor que el segundo para poder usarlo con este algoritmo.
El primer paso es comprobar si el segundo número es cero, en ese caso obviamente GCD es el primer número. Si ese no es el caso, entonces el segundo número se convierte en el primero y un mod b se convierte en el segundo número, por ejemplo, ahora necesitamos calcular GCD de 24 y 40 % 24, que es 16, es decir, GCD (24, 16), por lo que nuestro problema ahora se reduce.
Como el segundo número aún no es cero, pasamos al segundo paso nuevamente y esta vez, el algoritmo calcula MCD(16, 8) porque 24 % 16 = 8. Como 8 aún no es igual a cero, nuevamente pasamos al siguiente paso y esta vez, el algoritmo calcula GCD(8, 0) porque 16 mod 8 = cero. Ahora, el segundo número es cero, por lo tanto, el primer número es igual a GCD.
Entonces, finalmente, el MCD de 40 y 24 es igual a 8, lo cual es correcto porque es el número más grande que divide por completo tanto a 40 como a 24.
Aquí hay otro ejemplo del algoritmo euclidiano para calcular el máximo común divisor o el máximo común divisor:
Puede ver que el problema paso a paso se reduce a calcular el MCD de números más pequeños.
Programa Java para calcular LCM y GCF de dos números
Aquí está nuestro programa Java de muestra que encuentra el mínimo común más múltiplo y el máximo común divisor de dos números utilizando el método de Euclides. Este programa primero calcula GCD o GCF utilizando el algoritmo euclidiano y luego usa ese método para calcular el LCM o el mínimo común multiplicador.
Si desea obtener más información sobre los algoritmos de programación esenciales, le sugiero que lea un buen libro sobre estructuras de datos y algoritmos, por ejemplo, Introducción a los algoritmos de Thomas H. Cormen , que explica los algoritmos matemáticos y de programación clave en palabras sencillas.
Cálculo de LCM y GCD de dos números en Java
clase pública LCM {
public static void main( String [] args) {
System .out.println( "Bienvenido al programa Java para calcular
MCM y MCD de dos números" );
Scanner sc = new Scanner( System . in );
System .out.println( "Ingrese el primer número: " );
int n1 = sc.nextInt();
System .out.println( "Ingrese el segundo número: " );
int n2 = sc.nextInt();
int mcd = MCD(n1, n2);
int mcm = mcm (n1, n2);
System .out.println( "El máximo común divisor (MCD) de dos números
son: "
+ gcf);
Sistema .out
.println( "El mínimo común multiplicador (MCM) de dos números es: "
+ lcm);
Carolina del Sur. cerrar ();
}
/**
* Método Java para calcular el mínimo común multiplicador de dos números
*
* @param un
* @param b
* @return MCM de dos números
*/
public static int LCM( int a, int b) {
return (a * b) / GCF(a, b);
}
/**
* Método Java para calcular el máximo común divisor de dos números
*
* @param un
* @param b
* @return MCD de dos números usando el algoritmo de Euclides
*/
public static int GCF( int a, int b) {
if (b = = 0) {
return a;
} else {
return (GCF(b, a % b));
}
}
}
Producción
Bienvenido al Programa Java para calcular MCM y MCD de dos números
Introduzca el primer número :
40
Ingrese el segundo número :
24
El máximo común divisor (MCD) de dos números es : 8
El Mínimo Común Multiplicador (MCM) de dos números es : 120
Bienvenido al Programa Java para calcular MCM y MCD de dos números
Introduzca el primer número :
9
Ingrese el segundo número :
342
El máximo común divisor (MCD) de dos números es : 9
El Mínimo Común Multiplicador (MCM) de dos números es : 342
Eso es todo acerca de cómo encontrar el MCD y el MCM de dos números en Java . Es muy fácil de hacer con el algoritmo de Euclides porque una vez que tienes MCD, calcular LCM no es más que a*b/GCF(a,b) . Si desea más programas Java como este para practicar y mejorar su sentido de codificación y lógica de programación, consulte la siguiente lista de programas de entrevistas. Programas