SoloCodigo

Programación Específica => Diseño de Algoritmos => Mensaje iniciado por: BROTHYAM en Jueves 9 de Septiembre de 2010, 00:03

Título: Algoritmo Maximo comun divisor
Publicado por: BROTHYAM en Jueves 9 de Septiembre de 2010, 00:03
Hola a todos, quisiera que me ayuden a hacer un algoritmo para hallar el maximo común divisor de N numeros ¿Qué estructura repetitiva iría mejor para hacer eso?
Título: Re: Algoritmo Maximo comun divisor
Publicado por: Xinefpro en Viernes 5 de Noviembre de 2010, 02:57
Holas, te dejo 2 formas de resolver el problema:

* PRIMER METODO:

Existe una propiedad interesante del MCD, el cual sirve para el problema que mencionas:

Sean los enteros positivos: x[1], x[2], x[3], ..., x[n] ; entonces:

MCD( x[1], x[2], x[3], ..., x[n] ) = MCD( MCD( x[1], x[2], ..., x[n-1] ), x[n] )

Esto se puede aplicar recursivamente, hasta llegar a:

MCD( x[1], x[2], x[3], ..., x[n] ) = MCD( MCD( ... MCD( MCD( MCD( x[1], x[2] ), x[3] ), x[4]), ... ), x[n] )

En resumen para hallar el MCD de los N numeros, puedes intentar:

Primero calculas el MCD de x[1] y x[2], luego calculas el MCD del resultado anterior con x[3],
luego calculas el MCD del resultado anterior con x[4], asi sucesivamente hasta el ultimo numero x[n].

En pseudocogido seria asi:

Código: Java
  1.  
  2. Entero MCD = 1;
  3.  
  4. // MaximoComunDivisor( a, b ) es el algoritmo de euclides usado para
  5. // hallar el Maximo Comun Divisor de dos enteros positivos.
  6. Para i de 2 hasta n hacer
  7.    MCD = MaximoComunDivisor( MCD, x[i] )
  8.  
  9. Retornar MCD
  10.  
  11.  

* SEGUNDO METODO:

Otra propiedad del MCD dice que el máximo común divisor de dos números resulta ser el producto
de sus factores primos comunes elevados al menor exponente.
Es decir sean los numeros: 24, 30, 36

- 24 = ( 2^3 ) * (  3^1 )               = ( 2^3 ) * (  3^1 ) * ( 5^0 )
- 30 = ( 2^1 ) * ( 3^1 ) * ( 5^1 )   = ( 2^1 ) * ( 3^1 ) * ( 5^1 )
- 36 = ( 2^2 ) * ( 3^2 )                = ( 2^2 ) * ( 3^2 ) * ( 5^0 )

Por lo tanto el MCD( 24, 30, 36 ) = ( 2^1 ) * ( 3^1 ) * ( 5^0 ) = 6

Esto de puede modelar en un algoritmos, si es que guardamos cada numero en un vector de tamaño N,
y luego ir dividiendo todos los numeros del vector, entre 2, 3, 4, ..., Z, donde z es el menor numero almacenado en el vector:

Código: Java
  1.  
  2. // Vector donde estan almacenados los numeros de los que se hallara su MCD
  3. Entero[] vector           
  4. // Obtenemos el menor elemento del vector, el cual sera el maximo valor  por el que dividiremos cada elemento del vector.
  5. Entero menor = MenorElemento( vector )
  6. // Menor de todos los exponentes del factor primo actual
  7. Entero menorExponente = 0                  
  8. // Valor que almacena el MCD divisor de los numeros
  9. Entero MCD = 1                   
  10. // Indica si el factor primo actual es un divisor comun de todos los numeros
  11. Booleano esDivisorComun
  12.  
  13. // "i", indica el factor que verificaremos si es factor comun ( divisor ) a todos los numeros
  14. Para i desde 2 hasta i*i <= menor hacer
  15.      
  16.       esDivisorComun = verdad
  17.       j = 1
  18.       menorExponente = 0
  19.  
  20.       Mientras( esDivisorComun  )
  21.             Si( j = n + 1 )   // Si el divisor "i", es comun a todos entonces el menorExponente aumenta 1
  22.                 menorExponente = menorExponente + 1
  23.                 j = 1
  24.                
  25.                 // Como el i es divisor comun, pasamos a dividir todos los numeros entre i,
  26.                 // esto tambien afecta a "menor"
  27.                 Para  h de 1 hasta n hacer
  28.                      vector[ h ] = vector[ h ] / i
  29.                 FinPara
  30.  
  31.                 menor = menor / i
  32.             FinSi          
  33.                
  34.             Si( vector[ i ] mod i  != 0 )   // Si el divisor actual no es comun a todos, pasamos al siguiente divisor
  35.                 esDivisorComun = falso
  36.  
  37.        Fin_Mientras
  38.  
  39.        // Actualizamos el MCD
  40.        MCD = MCD * Potencia( i, menorExponente )
  41.  
  42. Fin_Para
  43.  
  44.  

Si comparamos los 2 algoritmos te puedes dar cuenta de que el primero es mas facil dec codificar ademas
que es de orden O( n log(n) ) , en cambio el segundo es mas "engorroso" para codificar y encima es de orden  O( n Raiz( n ) )
( lo cual es mas lento que el primer algoritmo ) .
Donde n es el valor del mayor elemento de los que se desea hallar su MCD.

Espero que te sirvan de algo.

PD: Realmente esos ordenes de los algortimos no son los correctos, ya que estos han sido calculados
en funcion del valor de n y no del tamaño de n.