Máximo común divisor... ¡de un arreglo!

[migsantiago]

Hola

Me dejaron de tarea realizar el máximo común divisor de una cantidad n de números en LabView. El hacerlo de forma gráfica es cansado y no sé cómo, así que quiero hacerlo en un Formula Node usando lenguaje C.

El dilema es que solo he encontrado cómo obtener el MCD para dos variables usando el método euclidiano...

Código: [Seleccionar]

unsigned int mcd(unsigned int a, unsigned int b){
     unsigned int aux;
     while (a > 0){
         aux = a;
         a = b % a;
         b = aux;
     }
     return b;
 }

... y pues mi necesidad es mayor. ¿Qué me recomiendan para lograrlo con n números?

Gracias

[Modulay]

Quizá la forma sea usando la técnica que se enseña en la escuela,aquella de descomponer en factores primos y tomar los factores comunes con el menor exponente (creo que era así)

[migsantiago]

Hola Modu

La forma que mencionas es ésta:

http://www.estudiantes.info/matematicas/maximo_comun_divisor.htm

Pero imagínate programar eso en lenguaje c 

Debe haber una forma amigable usando el método de Euclides pero para un arreglo... 

[Modulay]

Ciertamente el algoritmo y el uso de variables sería considerable,pero no se me ocurre otra forma.
Por la vía de Euclides no creas que se iba a simplificar mucho el asunto...quizá lo más viable fuera calcular todos los divisores de todos los números de origen y tomar el de mayor valor y que a la vez sea divisor de todos.
Creo que de la descomposición en producto de factores primos no te vas a librar

[migsantiago]

Ya veremos, ya veremos...   

Es que tengo el archivo .vi de un programa en labview que YA hace lo que me dejaron de tarea, pero el maestro le quitó el diagrama de bloques y no tengo ni idea de cómo funciona. Tengo que resolverlo a como dé lugar 

[Nocturno]

También podrías considerar hacerlo por fuerza bruta.

1- Empiezas utilizando como divisor el nº más bajo que tengas en tu array
2- Divides cada miembro del array por el divisor elegido hasta encontrar alguno que saque decimales.
3- Si alguno saca decimales, restas una unidad al divisor elegido y vuelves al paso 2
4- Si ninguno saca decimales, ya has encontrado tu MCD.

[ma4826]

Después de leer la idea de nocturno he tenido otra idea.

Otra posibilidad es factorizar el número menor y luego probar cada factor de este número con el resto, si algún número no es divisible descartas este factor y si todos son divisibles coges el factor y sigues el proceso con todos los números dividos por ese factor.

Por ejemplo:

(12,20,24)

12 -> 2*2*3

Probamos el primer 2:

Si son divisibles -> Tenemos un 2 -> nos queda (10,12)

Probamos el segundo 2:

Si son divisibles -> Tenemos otro 2 -> nos queda (5,6)

Probamos el 3:

Todos no son divisibles -> nos queda (5,6)

-> MCD = 2*2 = 4

Saludos,

Miguel Ángel.

[jfh900]

El máximo común divisor de tres números es:

mcd(a,b,c) = mcd(c, mcd(a,b))

Por inferencia se puede aplicar a cualquier cantidad de números. De esta forma utilizando el algoritmo de Euclides puedes resolver el problema.

Un saludo

[migsantiago]

Hola!

Nocturno y Miguel, es un buen método, pero consumiría mucho tiempo en procesador, pero creo que sí funcionaría, sobre todo el de Miguel que está un poco más resumido que el de Nocturno.

Jfh900, eso estaba pensando, que los MCD podían usarse iterativamente, ahora me toca convertirlo a labview+formula node 


Gracias, cuando lo termine publico el algoritmo en Labview 

[migsantiago]

¡Listo!

Adjunto el vi por si lo quieren abrir en su compu.

http://www.4shared.com/file/50128714/760bc7e6/Halla_MCD_semestre_A08.html

Primero hay que tener un arreglo con todos los números de los que uno quiere calcular su MCD, en mi caso lo llamé Tiempos. Luego se calcula el MCD entre los dos primeros elementos del arreglo...



Para forzar a que lo de arriba se ejecute primero pueden usar un stacked sequence structure. Luego en el siguiente frame se pone lo siguiente...



PunteroTiempos es solo el tamaño del arreglo Tiempos, se puede sustituir con un Array Size. Le resto 2 porque ya se había hecho el cálculo de los 2 primeros elementos.

Gracias por su ayuda 

[Geo]

Otra forma, parecida a las propuestas por Nocturno y Miguel .

1. Elegir el número menor como divisor.
2. Dividir a los restantes entre el divisor.
3. Si todas son divisiones exactas, tenemos el MCD.
4. Si alguna no es división exacta, calcular el mayor factor propio no evaluado del menor número.
5. Dicho factor es ahora el nuevo divisor.
6. Volver al paso 2.

Mmmm, no sé, podríamos probar varias formas y ver cuál es la más eficiente (para números pequeños, para números grandes, para pocos números, para muchos números, en gral., etc.) .

Con el ejemplo que puso Miguel
MCD de 12, 20, 24

Número menor: 12
20 mod 12 != 0, no es división exacta.
Mayor factor propio: 12 / 2 = 6
20 mod 6 != 0, no es división exacta
Siguiente factor propio: 12 / 3 = 4
20 mod 4 = 0, 24 mod 4 = 0
4 es el MCD.

[migsantiago]

Bueno, otra propuesta más, ahora sí ya hay de donde escoger jeje

Gracias Geo.