- Calculamos el residuo de dividir el valor más grande de ambos sobre el más pequeño
- Si el resultado es 0, entonces el resultado es el numero más pequeño de los anteriores
- En caso contrario reemplazamos el numero mayor con el residuo y volvemos al paso 1
Una implementación sencilla en Java:
public static int MCD(int a, int b) {
if(b == 0)
return 0;
return MCD(a, a % b);
}
¡¡¡Si alguien me hubiese dicho esto en secundaria no hubiese sufrido tanto con esas cosas!!!
Otro tip. Para obtener el MCM de a y b, basta con multiplicar a * b y dividir entre el MCD.
La complejidad del algoritmo es del orden de O (log n)
5 comentarios:
Hola, como va todo? me sorprendió realmente la implementacion hecha sobre "Maximo Comun Divisor", cuando lei el enunciado quise resolverlo por mi cuenta y tus 3 lineas fueron mucho mas elegantes que mis 12... ahora bien, entiendo que llamas recursivamente al procedimiento MCD con valores hasta que b sea = a 0 (corregime si me equivoco), pero en que momento se determina si a es mayor a b o viceversa? o directamente te pido el favor y me dejo de vueltas... me explicas como funciona?? Muchas gracias
es asi muerto!!!!
public static int MCD(int a, int b) {
int r;
if (a<b) {
r=a;
a=b;
b=r;
}
if(b == 0) return a;
return MCD(b, a % b);
}
Yo puse muchas mas lineas xd mira
public void MDC(int a, int b)
{
if ((a > b) && (b > 0))
{
c = a%b;
System.out.println(a + "/" + b + "= " + c);
if (c == 0)
{
System.out.println("El maximo comun divisor es: " + b);
}
MDC(b,c);
}
else
{
if ((b > a) && (a > 0))
{
c = b%a;
System.out.println(b + "/" + a + "= " + c);
if (c == 0)
{
System.out.println("El maximo comun divisor es: " + a);
}
MDC(a,c);
}
}
}
en java:
public long mcd (long a,long b)
{
if (b == 0) {return a;}
else {return mcd (b,(a % b));}
}
en haskell:
mcd::Int->Int->Int
mcd x 0 = x
mcd x y = mcd y (mod x y)
balenciaga
kyrie irving shoes
hermes birkin bag
jordan 12
air max 90
nike air force
air max 95
yeezy boost
moncler coat
air max 95
Publicar un comentario