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

Comentarios

Creo que a lo que se refiere con problemas es que al usar recursion la maquina debe hacer mas procesos debido al overheap de la recursion en donde se debe guardar los estados anteriores. https://stackoverflow.com/questions/4008595/recursion-overhead-how-seri….

Un codigo no recursivo seria el siguiente:

int gcd (int a, int b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}

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.