El mayor divisor común con Java
Significado del mayor divisor común
Un divisor es un número entero (entero) que entrará en otro número entero sin un resto. El mayor divisor común se explica mejor con una ilustración. La siguiente tabla muestra dos números: 60 y 108, con todos sus divisores mayores de 1.
Hay divisores en la tabla que no son comunes tanto a 60 como a 108. Sin embargo, 2 es un divisor común a los números 60 y 108, pero no es el mayor divisor común a 60 y 108. Divisor 3 se describe de manera similar. Mediante la inspección de la tabla, el mayor divisor que es común tanto para 60 como 108 es 12. Ningún divisor superior a 12 es común tanto en 60 como en 108. Entonces 12 es el mayor divisor común para 60 y 108.
El objetivo de este artículo es explicar cómo obtener el mayor divisor común por sustracción o por división; con programación realizada en Java.
GCD por resta
Por inspección de la tabla anterior, el GCD para 60 y 108 es 12. Esto significa que si 12 se agrega repetidamente, el resultado se convertirá en 60, el menor de ambos números. Si la adición de 12 continúa, el resultado se convertirá en 108, más grande de ambos números. Eso es:
12 + 12 +12 +12 + 12 = 60
12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108
Eso es:
60 + 12 + 12 + 12 + 12 = 108
Lo que significa:
60 + 48 = 108
Si la adición de GCD puede conducir a ambos números, entonces tal vez alguna forma de sustracción continua hacia abajo puede conducir al GCD. Este es un hecho, como se ilustra en los siguientes pasos, comenzando con la diferencia de 108 y 60:
108 - 60 = 48
60 - 48 = 12
48 - 12 = 36
36 - 12 = 24
24 - 12 = 12
12 - 12 = 0
Entre 60 y 108, 108 es el número más grande. Después de eso, la diferencia de la diferencia resultante (48 para el primer paso) y el subtrahend (60 para el primer paso) se obtiene repetidamente hasta que la respuesta es cero. En los pasos, se resta el número más pequeño, el número más grande. En el último paso, el Minuend y el Subtrahend son los mismos. Este mismo valor es el mayor divisor común.
Deje que los números cuyo GCD sea necesario sea A y B. Si estos números no tienen GCD mayor que 1, significa que su mayor divisor común es 1. En la programación, la complejidad del tiempo para encontrar el GCD por resta es O (A+B). Si A es 1 y B es 5, entonces los pasos sin programación serán:
5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0
El GCD aquí es 1. Hay cinco pasos aquí y no seis pasos de (A + B). Sin embargo, en la programación, el número máximo posible de operaciones de código es lo que se toma como la complejidad del tiempo.
Codificación de GCD por sustracción
La clase y el método para el mayor divisor común por resta en Java son:
clase GCDSint gcds (int a, int b)
if (a == b)
regresar a;
if (a> b)
retorno GCDS (A-B, B);
retorno GCDS (A, B-A);
Comienza con una declaración para el último paso matemático cuando ambos números resultantes son iguales. Las siguientes dos declaraciones restan el número más pequeño del número más grande recursivamente. Una clase principal de Java y el método principal de Java, para ir con la clase anterior, es:
clase pública Mainpublic static void main (string args [])
Gcds obj = new Gcds ();
int ret = obj.GCDS (108, 60);
Sistema.afuera.println (ret);
La salida es 12.
GCD por división
La tabla anterior se repite aquí para una fácil referencia:
Los dos números cuyo GCD es necesario son 60 y 108, siendo 108 el número más grande. La explicación anterior para la restauración comenzó con:
12 + 12 +12 +12 + 12 = 60
12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108
Eso es:
60 + 12 + 12 + 12 + 12 = 108
Lo que significa:
60 + 48 = 108
La división de Modulo es una división en la que la respuesta es la parte del número completo del cociente, y el resto también se tiene en cuenta. Considere el resto al dividir 108 por 60 y los restos de los cocientes resultantes y sus divisores correspondientes.
108 % 60 = 48 (i.E 1 R 48)
60 % 48 = 12 (i.E 1 R 48)
48 % 12 = 0 (i.E 4 R 0)
La división del módulo termina cuando el resto es 0. El GCD es el divisor para el último paso. Ya se sabía, del otro método anterior, que el mayor divisor común es 12.
108 mod 60 no es cero. Si el GCD entre 60 y 108 tuviera que ser encontrado por resta, la primera diferencia para el GCD entre 60 y 108 sería 48, y se puede demostrar que el GCD entre 60 y 108 es 12 es. 60 mod 48 no es cero. Si el GCD entre 60 y 48 (el resto anterior) tuviera que ser encontrado por resta, la primera diferencia para el GCD entre 60 y 48 sería 12, y se puede demostrar que el GCD entre 60 y 48 es 12 es. 48 mod 12 es cero y tiene 0 restos. Si el GCD entre 48 y 12 tuviera que ser encontrado por resta, la primera diferencia para el GCD entre 48 y 12 sería 36. 36 no es el GCD entre 48 y 12; Sin embargo, 36 es un múltiplo de 12, que es el GCD.
Usando cualquier medio, el lector puede probar con los pasos anteriores que dado que el GCD para 60 y 108 es 12, el GCD para 60 y 48 también es 12; y el GCD para 48 y 12 sigue siendo 12.
Considere otro ejemplo para encontrar el GCD por división. El problema ahora es: encontrar el GCD por división para los números 18 y 30.
Solución:
30 % 18 = 12 (i.mi. 1 R 12)
18 % 12 = 6 (i.mi. 1 R 6)
12 % 6 = 0 (i.mi. 2 r 0)
El GCD es 6, leído desde la última línea, donde el módulo es 0.
30 mod 18 no es cero. Si el GCD entre 30 y 18 tuviera que ser encontrado por subtracción, la primera diferencia para el GCD entre 30 y 18 sería 12, y se puede demostrar que el GCD entre 30 y 18 es 6 es 6. 18 mod 12 no es cero. Si el GCD entre 18 y 12 tuviera que ser encontrado por resta, la primera diferencia para el GCD entre 18 y 12 sería 6, y se puede demostrar que el GCD entre 18 y 12 es 6 es 6. 12 mod 6 es cero. Si el GCD entre 12 y 6 tuviera que ser encontrado por resta, la primera diferencia para el GCD entre 12 y 6 sería 6, y se puede demostrar que el GCD entre 12 y 6 es 6 es 6. 6 es también un múltiplo de 6, que es el GCD.
Usando cualquier medio, el lector puede probar con los pasos anteriores que dado que el GCD para 30 y 18 es 6, el GCD para 18 y 12 también es 6; y el GCD para 12 y 6 sigue siendo 6.
Ahora considere el GCD obtenido de 1 y 5 por división:
5 % 1 = 0 (i.mi. 5 r 0)
Solo hay un paso (una línea) aquí. Para finalizar esta sección, tenga en cuenta que el divisor en la última línea, al buscar el GCD por división, es el GCD.
Además, tenga en cuenta que:
GCD (A, B) = GCD (B, R)
donde "A" y "B" son dos números enteros diferentes y "R" es el resto de la división entre A y "B."" B "puede ser más grande que" A "o" A "puede ser más grande que B. Esto significa que si el resto de una división no es cero, entonces el mayor divisor común entre los dos números es el mismo que el mayor divisor común entre el divisor y el resto. La prueba de esta declaración se ha ilustrado arriba.
Esto puede ir directamente por la división Modulo, como se experimenta anteriormente hasta que el resto sea cero. Cuando el resto es cero, esta regla de repetición no se mantiene. Estrictamente hablando, en la división del módulo, no importa si "A" es más grande que B o B es más grande que "A"; el resto es el mismo entero positivo.
Codificación de GCD por división
Si el mayor divisor común por la división entre 60 y 108 se requiere matemáticamente, entonces los pasos serían
108 % 60 = 48 (i.E 1 R 48)
60 % 48 = 12 (i.E 1 R 48)
48 % 12 = 0 (i.E 4 R 0)
Observe que es el número más grande el que se divide, el número más pequeño. La clase y el método Java para hacer esta división es:
Clase GCDDint gcdd (int a, int b)
if (a % b == 0)
regreso B;
retorno GCDD (b, A % B);
La primera declaración en el método representa el último paso matemático. La segunda declaración hace la división del módulo. Ambas declaraciones llaman al método de manera recursiva. La complejidad del tiempo para GCD por división es O (log (a + b)). Una buena clase principal y el método principal para este código son:
clase pública Mainpublic static void main (string args [])
Gcdd obj = new GCDD ();
int ret = obj.GCDD (108, 60);
Sistema.afuera.println (ret);
La salida es 12.
Conclusión
El mayor divisor común se puede obtener restando primero el número más pequeño del número más grande y luego continúa restando la minuenda de la diferencia o la diferencia del minUnde, dependiendo de qué número sea mayor.
El mayor divisor común también se puede obtener dividiendo primero el número más grande por el número más pequeño utilizando la división del módulo; y luego continuar dividiendo el resto por el divisor o el divisor por el resto, dependiendo de cuál sea más grande, aún por la división del módulo. Estrictamente hablando, en la división del módulo, no importa si "A" es más grande que B o B es más grande que "A"; el resto es el mismo entero positivo.
Esto se realiza programáticamente recursivamente.