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.
Comentarios
la recursividad puede llegar…
la recursividad puede llegar a dar problemas por lo que sería mejor hacerlo con un bucle while:
int mcd(int a,int b){
while(b!=0){
int aux=b;
b=a%b;
a=aux;
}
return a;
}
Hola, por que podría dar…
Hola, por que podría dar problemas? A que se refiere con eso ?
En respuesta
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