domingo, 4 de mayo de 2008

Máximo Común Divisor.

Una forma computacionalmente simple de evaluar el Máximo Común Divisor de dos números es una simple técnica de restas:


  1. Calculamos el residuo de dividir el valor más grande de ambos sobre el más pequeño

  2. Si el resultado es 0, entonces el resultado es el numero más pequeño de los anteriores

  3. 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)