Algoritmo de Euclides

Enviado por fmoreno el Dom, 22/09/2019 - 19:51

El algoritmo de Euclides es un conocido algoritmo para calcular el máximo común divisor de dos números. Se basa en la siguiente propiedad: $\text{mcd}(a, b) = \text{mcd}(a-b, b)$. Así, si se va sustrayendo el número menor de el número mayor, cada vez los pares de números que quedan se van haciendo más pequeños hasta que uno de los números es $0$, y $\text{mcd}(a, 0) = a$. 

Por ejemplo, para calcular el máximo común divisor de $105$ y $70$:

\[ \text{mcd}(105, 70) = \text{mcd}(105-70, 70) = \text{mcd}(35, 70) = \text{mcd}(35, 70-35) = \text{mcd}(35, 35) = \text{mcd}(35, 35-35) = \text{mcd}(35, 0) = 35 \]

Se puede programar de forma muy sencilla utilizando recursividad:

int mcd(int a, int b) {
    if(b == 0) return a;
    return mcd(b, a%b);
}
def gcd(a, b):
	if b == 0: return a
	return gcd(b, a%b)

La función retorna el máximo común divisor de $a$ y $b$. Si $b$ es $0$, el resultado es $a$; si no, la función se llama recursivamente con un valor de $b$ estrictamente menor (de esa forma la recursividad acabará llegando a un final). Aquí hemos utilizado el operador módulo (%), que da el resto de a cuando se divide por $b$. Esto es porque tras restar $b$ de $a$ tantas veces como sea necesario para que el resultado sea menor que $a$, lo que queda es el resto de dividir a entre $b$. Nótese que si llamamos a la función con $b > a$, en la primera llamada recursiva se intercambiarán los dos valores y se calculará el $\text{mcd}$ correctamente. 

Printer Friendly, PDF & Email

Añadir nuevo comentario

Texto sin formato

  • No se permiten etiquetas HTML.
  • Saltos automáticos de líneas y de párrafos.
  • Las direcciones de correos electrónicos y páginas web se convierten en enlaces automáticamente.