El algoritmo de Euclides es un método para obtener el máximo común divisor (MCD) de dos números, descrito por el matemático griego Euclides alrededor del año 300 A.C. Con una pequeña modificación, este algoritmo también puede utilizarse para encontrar el Mínimo Común Multiplo (MCM) de dos números.
En programación, podemos implementar el algoritmo de Euclides sin muchas complicaciones, siendo una de sus aplicaciones el simplificar fracciones hasta su minima expresión.
A continuación, te muestro como implementar el algoritmo de Euclides en Python para obtener el Máximo Común Divisor y el Mínimo Común Multiplo de dos números.
Te puede interesar:
Descripción del algoritmo de Euclides
Antes de comenzar a programar nuestro algoritmo, es necesario comprender como funciona.
El algoritmo de Euclides dice que, con a y b como enteros positivos, y siendo siempre a > b:
- Se divide
a ÷ b, obteniendo un residuo enteror1y un cocienteq1 - Se demuestra que
a = q1· b + r1, por lo que ahoraa = b y b = r1. Repetimos el primer paso, obteniendor2yq2. - Se repiten los pasos hasta que el residuo resultante sea igual a
0(rn == 0), siendo el último residuo obtenido antes del0(rn-1) el Máximo Comun Divisor de los números.
Aplicando el anterior algoritmo en un ejemplo:
- Tomando
a = 1224;b = 221;qn = a ÷ b(entero) ; =rn = a % b -
Paso Ecuación Cociente y residuo 0 1224 = q0 · 221 + r0 q0 = 5 ; r0 = 119 1 221 = q1 · 119 + r1 q1 = 1 ; r1 = 102 2 119 = q2 · 102 + r2 q2 = 1 ; r2 = 17 3 102 = q3 · 17 + r3 q3 = 6 ; r3 =0 Máximo Comun Divisor = 17
En programación, podemos simplificar el proceso aprovechando el operador modulo ( % ), como se ve a continuación.
Implementar algoritmo de Euclides en Python 3
Uno de los acercamientos más simples al algoritmo de Euclides en Python es aprovechando la recursividad para obtener la respuesta sin necesidad de bucles y en pocas líneas:
https://gist.github.com/anonymous/9a225603e6416edb7c219a0a435efa01
En la función anterior, si el valor de b es igual a 0, regresamos el valor de la variable a, si esto no es así, volvemos a llamar a la función, esta vez reemplazando el valor de a por el de b, y el valor de b por el residuo de a ÷ b
Cuando b == 0, se llega al último nivel de la recursión, y se regresa el valor de a en ese momento, que será rn-1 mostrado en la descripción del algoritmo.
De igual forma, podemos expresar el algoritmo de Euclides de manera iterativa en Python utilizando un sólo bucle while:
https://gist.github.com/anonymous/1695cbd18cb9c18b8f8d4a6bbdb264b6
En esta función, mientras el residuo de a ÷ b no sea igual a 0, las variables old_a y old_b tomaran el valor de a y b, respectivamente, mientras que a tomará el anterior valor de b (almacenado en old_b), y b será igual al residuo entre el anterior valor de a y el anterior valor de b (old_a % old_b).
Cuando el residuo de a ÷ b sea 0, se detendrá la asignación de variables y se regresará el valor de b, que será rn-1 mostrado en la descripción del algoritmo de Euclides.
Una tercer forma de implementar el algoritmo en Python, es mediante el uso de una función anónima lambda, con la siguiente línea de código:
https://gist.github.com/anonymous/6600b9903dbc9f9f9ba5c574ec4c4fd2
Que no es más que nuestra función recursiva condensada en una línea de código.
Si lo que buscamos es el Mínimo común multiplo (MCM) de dos números, tan sólo tenemos que cambiar ligeramente el algoritmo para hacer lo siguiente: a · MCD (a, b) · b
En código:
https://gist.github.com/anonymous/7203e46e07c127f710c0d0ee44c935a9
Finalmente, aquí puedes ejecutar y probar el código:
Fuente: Problem Solving with Algorithms and Data Structures using Python
Libros que te pueden interesar:
 |
 |
 |
| Python for Data Analysis | Python Data Structures and Algorithms | Python Algorithms |
Deja una respuesta