mar 21 2011
Máximo común divisor y mínimo común múltiplo según Euclides
Euclides fue un matemático griego que vivió desde el año 325 hasta el 265 a.C. También es conocido como el padre de la geometría. La cuestión es que el patín este, en una de sus tantas masturbaciones cerebrales, eyaculo un método muy eficaz para calcular el máximo común divisor de 2 números; es decir, cualquiera de nosotros, mediante la forma que nos fue enseñada en el colegio, es capaz de hacer un programa para que calcule el máximo común divisor de 2 números, pero la cuestión es que, Euclides ideó un algoritmo que lo hace con menor cantidad de operaciones, ósea de menor complejidad computacional en comparación al algoritmo clásico del MCD.
El algoritmo comprende de pocas operaciones, sin embargo Euclides debe haber tenido una gran imaginación para encontrar una relación entre el MCD y la operación de modulo o resto; siendo esta ultima operación sobre la que este algoritmo basa su funcionamiento. Su implementacion en el lenguaje de programación Java es como sigue:
public static int gcd(int m, int n)
{
int r;
while(n!=0)
{
r = m%n;
m = n;
n = r;
}
return m;
}
Y tambien esta su implementacion recursiva:
public static int gcdRecursivo(int a, int b)
{
if(b==0)
return a;
else
return gcdRecursivo(b, a%b);
}
Y una mas de yapa que no es optima y que la hice a la manera tradicional, como nos la enseñaron en el colegio:
public static int mcd(ArrayList<Integer> inputList)
{
ArrayList<Integer> listaDivisores = new ArrayList<Integer>();
ArrayList<Integer> listaTemp = new ArrayList<Integer>();
Collections.sort(inputList);
int divisor = inputList.get(0);
int mcd = 1;
boolean band = false;
while(divisor>0)
{
for(int n:inputList)
{
if(n % divisor!=0)
{
band = false;
break;
}
else
{
band = true;
listaTemp.add(n/divisor);
}
}
if(band==true)
{
inputList = new ArrayList<Integer>(listaTemp);
listaDivisores.add(divisor);
band = false;
}
divisor--;
listaTemp.clear();
}
for(int m:listaDivisores)
mcd *= m;
return mcd;
}
El metodo de Euclides para hallar el MCD, tambien sirve como base para hallar el MCM, por ejemplo:
Sean a = 12, b = 15. Entonces
mcm(12,15) = (12)(15)/ mcd(12,15)
= 180/3
= 60
Cuya implementacion en Java es la siguiente:
public static int mcm(int a, int b)
{
return (a*b)/gcd(a,b);
}
Eso fue para 2 entradas, ahora hagamoslo para N entradas de forma iterativa:
public static int mcmIterativo(LinkedList<Integer> inputList)
{
int mcm = -1;
while(inputList.size()>=2)
{
Collections.sort(inputList);
mcm = mcm(inputList.get(0),inputList.get(1));
inputList.removeFirst();
inputList.removeFirst();
inputList.add(mcm);
}
return mcm;
}
Y tambien de forma recursiva:
public static int mcmRecursivo(int a, LinkedList<integer> inputList)
{
Collections.sort(inputList);
if(inputList.size()==2)
return mcm(inputList.get(0),inputList.get(1));
else
{
int m = inputList.removeFirst();
int n = inputList.removeFirst();
inputList.add(mcm(m, n));
return mcmRecursivo(mcm(m, n), inputList);
}
}
En fin, quizas Euclides nunca se imagino que su algoritmo para hallar el MCD fuera tan popular hasta estos tiempos y que sirviera en un area de la informática tan importante como lo es la criptografia; pero la verdad es que sin estos locos matematicos, la informática no existiría.
