El mayor divisor común con Python
Un factor es un número que puede entrar en otro número sin un resto. Un dividendo divide un divisor para dar el cociente. Si el dividendo y el divisor son un número completo y si el cociente tiene un resto de cero (sin resto), entonces el divisor se llama factor del dividendo. El mayor divisor común se abrevia, g.C.D o simplemente GCD. Otro nombre para el mayor divisor común es el factor común más alto, abreviado h.C.F.
Encontrar G.C.F por definición
El problema es encontrar el factor común más alto también llamado el mayor divisor común para los números 108 y 240.
Solución:
Todos los factores mayores que 1 se colocan en la siguiente tabla:
108: 2 3 4 6 9 12 18 27 36 54 108
240: 2 3 4 5 6 8 10 12 15 16 20 24 30 48 60 120 240
La primera fila tiene los factores de 108 en orden ascendente. La segunda fila tiene los factores de 240 en orden ascendente.
Los factores comunes (divisores) para 108 y 240 son: 2, 3, 4, 6 y 12.
Por inspección, el mayor factor (divisor) que es común a los números 108 y 240 es 12. Es decir, GCD o H.C.F para 108 y 240 es 12.
Escribir un programa que encontrará el GCD, como se explicó anteriormente, llevará demasiado tiempo. Dos métodos más cortos para encontrar el GCD son: GCD por resta y GCD por división.
GCD por resta
Por inspección de la tabla anterior, GCD para 108 y 240 es 12. Esto significa que si 12 se agrega repetidamente, el resultado se convertirá en 108, que es el más pequeño de ambos números. Si la adición de 12 continúa, entonces el resultado se convertirá en 240, que es el más grande de ambos números. Eso es:
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240
Eso es:
108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240
Lo que significa:
108 + 132 = 240
Si el GCD se puede agregar repetidamente para dar cualquiera de los números (108 y 240) de los cuales se requiere el GCD, entonces podría ser posible hacer algún tipo de resta en repetidas ocasiones, comenzando con los números dados para tener el GCD. De hecho, es posible hacer un tipo particular de resta en repetidas ocasiones y obtener el GCD. Esto comienza con la diferencia de los números dados.
Problema: Encuentre el mayor divisor común (factor común más alto) para 108 y 240 por sustracción.
Solución:
240 - 108 = 132
132 - 108 = 24
108 - 24 = 84
84 - 24 = 60
60 - 24 = 36
36 - 24 = 12
24 - 12 = 12
12 - 12 = 0
Entre 108 y 240, 240 es el número más grande. Después de la diferencia de estos números dados, la diferencia de la diferencia resultante (132 para el primer paso) y el subtrahend (108 para el primer paso) se obtienen repetidamente hasta que la diferencia final es cero. En los pasos, el número más pequeño se resta del 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 6, entonces los pasos sin programación serán:
6 - 1 = 5
5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0
El GCD aquí es 1. Hay seis pasos aquí y no siete 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 función para el mayor divisor común por resta, en Python, es:
def gcds (a, b):
Si a == b:
devolver un
Si A> B:
Return GCDS (A - B, B)
demás:
devolver GCD (A, B - A)
La primera declaración se encarga del último paso matemático. La siguiente declaración de compuesto (si/else) hace la resta entre la minuenda y la diferencia, dependiendo de cuál sea más grande.
Mira en profundidad a las subtracciones de matemáticas GCD
240 - 108 = 132
132 = 12 x 11 (132 tiene 12 como factor)
132 - 108 = 24
24 = 12 x 2 (24 tiene 12 como factor)
108 - 24 = 84
84 = 12 x 7 (84 tiene 12 como factor)
84 - 24 = 60
60 = 12 x 5 (60 tiene 12 como factor)
60 - 24 = 36
36 = 12 x 3 (36 tiene 12 como factor)
24 - 12 = 12
12 = 12 x 1 (12 tiene un factor o 12, en sí mismo)
24 - 12 = 12
12 = 12 x 1 (12 tiene un factor o 12, en sí mismo)
El último paso tiene una diferencia de 0. Marca el final de los pasos de resta y le da al GCD como subrahend o minUd.
GCD por división
Entre 108 y 240, el GCD es mayor que 1.
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240
Eso es:
108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240
Lo que significa:
108 + 132 = 240
Eso es:
12 x 9 + 12 x 11 = 240
Además, 108 = 12 x 9 y 240 = 12 x 20.
Ahora, si el GCD puede multiplicarse por un número completo (entero positivo) para dar cualquiera de los números (108 o 240) de los cuales se requiere el GCD, entonces podría ser posible hacer algún tipo de división repetidamente, comenzando con el Números dados para tener el GCD. De hecho, es posible hacer un tipo particular de división repetidamente y obtener el GCD. Esta división es una división especial de módulos repetitivos. Comienza con la división del módulo de los números dados.
En la división del módulo, cuando el dividendo está dividido por el divisor, el resto del cociente es la respuesta.
Problema: Encuentre el mayor divisor común (factor común más alto) para 108 y 240 por división de módulo:
Solución:
240 % 108 = 24 (i.mi. 2 R 24)
108 % 24 = 12 (i.mi. 4 r 12)
24 % 12 = 0 (i.mi. 2 r 0)
En la última línea, donde el resto es cero, el divisor es el mayor divisor común (factor común más alto).
Este problema es encontrar el GCD entre 108 y 240 por división. La solución aquí dio 3 pasos. El problema anterior era similar, pero era buscar el mismo GCD por resta; Y tenía 8 pasos. Si bien la complejidad del tiempo para el método de sustracción es O (A + B), la complejidad del tiempo para el método de división es O (log (a + b)).
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.
Encuentre matemáticamente, el mayor divisor común por división, para los números, 5 y 2.
Solución:
5 % 2 = 1
1 % 1 = 0
El GCD es 1. Esto necesitaba dos pasos matemáticos.
Codificación de GCD por división
La palabra, "división" aquí se refiere a la división del módulo. La función es:
Def GCDD (A, B):
if (a % b == 0):
regreso b
demás:
Devolver GCDD (b, A % b)
El IF-PART del if/else-constructo se encarga de la última declaración matemática, para los pasos de la división del módulo. La parte de lo contrario se encarga de la división de módulo real (lo que resulta en el resto). 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.
Para llamar e imprimir un GCD, se puede usar el siguiente código:
Ret = GCDD (240, 108)
print (ret, end = '\ n')
Mira en profundidad a las divisiones de matemáticas GCD
240 % 108 = 24 (el GCD entre 240 y 108 es 12)
24 = 12 x 2 (24 tiene 12 como factor)
108 % 24 = 12 (el GCD entre 108 y 24 es 12)
12 = 12 x 1 (12 tiene 12 como factor, en sí mismo)
24 % 12 = 0 (el GCD entre 24 y 12 es 12)
Se ha demostrado aquí 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. Por lo tanto, si el resto de una división no es cero, entonces el mayor divisor común entre los dos números dados es el mismo que el mayor divisor común entre el divisor y el resto. Esto se agota en diferentes pasos hasta que el resto sea cero, incluso si el GCD es 1.
El último paso tiene un resto de 0. Marca el final de los pasos de la división del módulo y el GCD es el divisor.
Conclusión
El mayor divisor común puede determinarse mediante restaciones repetidas o divisiones de módulos repetidas.
Si es por sustracción, entonces después de la resta de los números dados, el resto de las restauraciones están entre la diferencia y la minuenda, dependiendo de cuál sea más grande. Cuando la diferencia es cero, el subtrahend es igual al minUnd, y cualquiera es el GCD.
Si es por división, entonces las divisiones repetidas son divisiones de módulo. En esta situación, después de la división del módulo de los números dados, el resto de las divisiones del módulo están entre el divisor y el resto, dependiendo de cuál sea más grande. Cuando el resto es cero, el divisor es el GCD. 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.