Programación Específica > Diseño de Algoritmos
Algoritmo Maximo comun divisor
(1/1)
BROTHYAM:
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?
Xinefpro:
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 --- Entero MCD = 1; // MaximoComunDivisor( a, b ) es el algoritmo de euclides usado para // hallar el Maximo Comun Divisor de dos enteros positivos.Para i de 2 hasta n hacer MCD = MaximoComunDivisor( MCD, x[i] ) Retornar MCD
* 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 --- // Vector donde estan almacenados los numeros de los que se hallara su MCDEntero[] vector // Obtenemos el menor elemento del vector, el cual sera el maximo valor por el que dividiremos cada elemento del vector.Entero menor = MenorElemento( vector )// Menor de todos los exponentes del factor primo actualEntero menorExponente = 0 // Valor que almacena el MCD divisor de los numerosEntero MCD = 1 // Indica si el factor primo actual es un divisor comun de todos los numerosBooleano esDivisorComun // "i", indica el factor que verificaremos si es factor comun ( divisor ) a todos los numerosPara i desde 2 hasta i*i <= menor hacer esDivisorComun = verdad j = 1 menorExponente = 0 Mientras( esDivisorComun ) Si( j = n + 1 ) // Si el divisor "i", es comun a todos entonces el menorExponente aumenta 1 menorExponente = menorExponente + 1 j = 1 // Como el i es divisor comun, pasamos a dividir todos los numeros entre i, // esto tambien afecta a "menor" Para h de 1 hasta n hacer vector[ h ] = vector[ h ] / i FinPara menor = menor / i FinSi Si( vector[ i ] mod i != 0 ) // Si el divisor actual no es comun a todos, pasamos al siguiente divisor esDivisorComun = falso Fin_Mientras // Actualizamos el MCD MCD = MCD * Potencia( i, menorExponente ) Fin_Para
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.
Navegación
Ir a la versión completa