En este ejemplo, aprenderá a encontrar el MCD de dos números utilizando dos métodos diferentes: función y bucles y algoritmo euclidiano.
Para comprender este ejemplo, debe tener el conocimiento de los siguientes temas de programación de Python:
- Funciones de Python
- Recursión de Python
- Argumentos de la función Python
El máximo común divisor (HCF) o máximo común divisor (MCD) de dos números es el entero positivo más grande que divide perfectamente los dos números dados. Por ejemplo, el HCF de 12 y 14 es 2.
Código fuente: uso de bucles
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Salida
El HCF es 6
Aquí, dos enteros almacenados en las variables num1 y num2 se pasan a la compute_hcf()función. La función calcula el HCF de estos dos números y lo devuelve.
En la función, primero determinamos el menor de los dos números, ya que el HCF solo puede ser menor o igual al número más pequeño. Luego usamos un forbucle para ir de 1 a ese número.
En cada iteración, verificamos si nuestro número divide perfectamente ambos números de entrada. Si es así, almacenamos el número como HCF. Al finalizar el ciclo, terminamos con el número más grande que divide perfectamente ambos números.
El método anterior es fácil de entender e implementar, pero no es eficiente. Un método mucho más eficiente para encontrar el HCF es el algoritmo euclidiano.
Algoritmo euclidiano
Este algoritmo se basa en el hecho de que HCF de dos números también divide su diferencia.
En este algoritmo, dividimos el mayor por el menor y tomamos el resto. Ahora, divide el más pequeño por este resto. Repita hasta que el resto sea 0.
Por ejemplo, si queremos encontrar el HCF de 54 y 24, dividimos 54 entre 24. El resto es 6. Ahora, dividimos 24 entre 6 y el resto es 0. Por lo tanto, 6 es el HCF requerido.
Código fuente: uso del algoritmo euclidiano
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Aquí hacemos un bucle hasta que y se convierte en cero. La declaración x, y = y, x % yintercambia valores en Python. Haga clic aquí para obtener más información sobre el intercambio de variables en Python.
En cada iteración, colocamos el valor de y en x y el resto (x % y)en y, simultáneamente. Cuando y se vuelve cero, tenemos HCF en x.
