Algoritmo de Euclides en Python

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:

  1. Se divide a ÷ b, obteniendo un residuo entero r1 y un cociente q1
  2. Se demuestra que a = q1· b + r1, por lo que ahora a = b y b = r1. Repetimos el primer paso, obteniendo r2 y q2.
  3. Se repiten los pasos hasta que el residuo resultante sea igual a 0 (rn == 0), siendo el último residuo obtenido  antes del 0 (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:

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:

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:

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:

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

Tags:

Share Post :

More Posts