/html/espaniol/Apuntes/2014-01-15-AlgoritmoMaximoComunDivisor/MCD-B.jpg

Algoritmo para hallar el Máximo Común Divisor.

   Miercoles 15, de Enero del 2014
 

 

El primer algoritmo para hallar el máximo común divisor de dos números lo planteo Euclides, pero como una serie de restas sucesivas. Su algoritmo erá un método para hallar de dos segmentos dados, un segmento con una medida máxima que pueda estar contenido en ambos segmentos.

El algoritmo consiste, en que dados dos números naturales A y B, en donde A es mayor que B, se debe ir restando B de A, hasta obtener un número menor que B o un 0, si obtenemos un 0 entonces B es el máximo común divisor, pero si se obtuvo un número menor que B, entonces se vuelve a repetir la operación, haciendo que B sea ahora el número mayor A y el número menor obtenido será B. Veamos un ejemplo:

 

    Algoritmo para hallar el determinante de una matriz nxn en Free Pascal - 01.

 

Con esto podemos ya hacer un primer algoritmo, que se muestra a continuación:

 

 
function mcd01(n1,n2:qword):qword;
 var A,B:qword;
 Begin
   A:=n1;
   B:=n2;
   if n2>n1 then Begin A:=n2;B:=n1 end;
   while A<>B do
     Begin
      if A>B
         then A:=A-B
         else B:=B-A
     end;
   mcd01:=B
 End;
 

Código fuente 1: Primer algoritmo del MCD según Euclides.

 

En este primer algoritmo se hacen una serie de comprobaciones, primero debemos asegurarnos que el numero mayor, siempre será A y el menor siempre será B. Eso se hace con la instrucción:

 

if n2>n1 then Begin A:=n2;B:=n1 end;

 

Luego de esas verificaciones se comprueba si son iguales, si en caso fueran iguales entonces cualquiera de los dos números sería el máximo común divisor, con lo que no es necesario ejecutar las restas sucesivas del bucle while. En caso contrario fueran diferentes entonces se ejecuta las instrucciones del bucle while. Las instrucciones dentro del bucle while, serán las que se encargarán de ir restando e intercambiando los valores de A y B, hasta obtener el Máximo Común Divisor que quedará almacenado en B. Por si no se han dado cuenta, este bucle termina cuando ambos números A y B son iguales ya que al ser iguales se obtendrá el 0, que nos indica que ya no se debe seguir restando e intercambiando los números.

Si probamos la función con los números del ejemplo, entonces obtendremos el 16, pero si usamos la función con números tan grandes como 18446744073709551615 y 18446744073709551010, veremos que este se demorará demasiado en obtener el MCD, esto es debido a que el algoritmo realiza demasiadas restas conformen los números son más grandes o tengan más cifras. Esto nos obliga a buscar otras opciones.

Tal como podemos observar en el algoritmo, cada vez que hacemos restas sucesivas lo que estamos haciendo en realidad es una división, y la última resta que obtenemos es en realidad el residuo. Es decir que 128 es el residuo de dividir 560 entre 432, 48 es el residuo de dividir 432 con 128, 32 el residuo de dividir 128 con 48, 16 el residuo de dividir 48 entre 32 y finalmente 0 es el residuo de dividir 32 entre 16. Al cambiar las restas sucesivas del algoritmo por el uso de residuos, entonces el algoritmo se hace más eficiente y mucho más rápido, tal como lo demostró Gabriel Lamé en 1844. Veamos el mismo ejemplo con residuos:

 

    Algoritmo para hallar el determinante de una matriz nxn en Free Pascal - 01.

 

Tal como se puede observar el algoritmo es mucho más rápido y bastante sencillo de implementar, sólo se necesita hacer un bucle con divisiones sucesivas hasta obtener una división exacta, que nos de como residuo un 0. Con esto ya podemos implementar el siguiente algoritmo:

 

 
function mcd02(n1,n2:qword):qword;
var A,B:qword;
    residuo:qword;
Begin
   A:=n1;
   B:=n2;
   if A<>B then
     Begin
      if n2>n1 then Begin A:=n2;B:=n1 end;
      residuo:=A mod B;
      While residuo<>0 do
       Begin
        A:=B;
        B:=residuo;
        residuo:=A mod B;
       End;
     End;
   mcd02:=B;
End;
 

Código fuente 1: Primer algoritmo del MCD según Euclides.

 

La principal diferencia entre el algoritmo anterior con este, esta en que se usa un bucle while que verifica si el residuo es cero o no, y cuando es cero entonces el último residuo obtenido es el M.C.D, que queda almacenado en B.

El siguiente archivo mcd.pp, implementa los algoritmos antes mencionados y el siguiente archivo mcd.java es la versión en java.

Referencias:

 

http://es.wikipedia.org/wiki/Algoritmo_de_Euclides

http://huitoto.udea.edu.co/SistemasDiscretos/contenido/alg_euclides.html

 

Delicious

 

 

 
 

  COMENTARIOS