Máximo divisor común euclídeo para más de dos números

Question

¿Alguien puede dar un ejemplo para encontrar el mayor algoritmo divisor común para más de dos números?

Creo que el lenguaje de programación no importa.

Answer 1

Comience con el primer par y obtenga su MCD, luego tome el MCD de ese resultado y el siguiente número. La optimización obvia es que puedes parar si el GCD en ejecución llega a 1. Estoy viendo esto para ver si hay otras optimizaciones. :)

Ah, y esto se puede paralelizar fácilmente ya que las operaciones son conmutativas / asociativas.

Answer 2

El MCD de 3 números se puede calcular como gcd (a, b, c) = gcd (gcd (a, b), c) . Puede aplicar el algoritmo euclidiano, el algoritmo euclidiano extendido o el binario GCD de forma iterativa y obtener su respuesta. Desafortunadamente, no conozco ninguna otra forma (¿más inteligente?) De encontrar un MCD.

Answer 3

Un poco tarde para la fiesta, lo sé, pero una simple implementación de JavaScript, utilizando la descripción del algoritmo de Sam Harwell:

function euclideanAlgorithm(a, b) {
    if(b === 0) {
        return a;
    }
    const remainder = a % b;
    return euclideanAlgorithm(b, remainder)
}

function gcdMultipleNumbers(...args) { //ES6 used here, change as appropriate
  const gcd = args.reduce((memo, next) => {
      return euclideanAlgorithm(memo, next)}
  );

  return gcd;
}

gcdMultipleNumbers(48,16,24,96) //8

Answer 4

En Java (no óptimo):

public static int GCD(int[] a){
    int j = 0;

    boolean b=true;
    for (int i = 1; i < a.length; i++) {
        if(a[i]!=a[i-1]){
            b=false;
            break;
        }
    }
    if(b)return a[0];
    j=LeastNonZero(a);
    System.out.println(j);
    for (int i = 0; i < a.length; i++) {
        if(a[i]!=j)a[i]=a[i]-j;
    }
    System.out.println(Arrays.toString(a));
    return GCD(a);
}

public static int LeastNonZero(int[] a){
    int b = 0;
    for (int i : a) {
        if(i!=0){
            if(b==0||i<b)b=i;
        }
    }
    return b;
}

Answer 5

Acabo de actualizar una página Wiki sobre esto.

[ https://en.wikipedia.org/wiki/Binary_GCD_algorithm# C.2B.2B_template_class]

Esto toma un número arbitrario de términos. use GCD (5, 2, 30, 25, 90, 12);

template<typename AType> AType GCD(int nargs, ...)
{
    va_list arglist;
    va_start(arglist, nargs);

    AType *terms = new AType[nargs];

    // put values into an array
    for (int i = 0; i < nargs; i++) 
    {
        terms[i] = va_arg(arglist, AType);
        if (terms[i] < 0)
        {
            va_end(arglist);
            return (AType)0;
        }
    }
    va_end(arglist);

    int shift = 0;
    int numEven = 0;
    int numOdd = 0;
    int smallindex = -1;

    do
    {
        numEven = 0;
        numOdd = 0;
        smallindex = -1;

        // count number of even and odd
        for (int i = 0; i < nargs; i++)
        {
            if (terms[i] == 0)
                continue;

            if (terms[i] & 1)
                numOdd++;
            else
                numEven++;

            if ((smallindex < 0) || terms[i] < terms[smallindex])
            {
                smallindex = i;
            }
        }

        // check for exit
        if (numEven + numOdd == 1)
            continue;

        // If everything in S is even, divide everything in S by 2, and then multiply the final answer by 2 at the end.
        if (numOdd == 0)
        {
            shift++;
            for (int i = 0; i < nargs; i++)
            {
                if (terms[i] == 0)
                    continue;

                terms[i] >>= 1;
            }
        }

        // If some numbers in S  are even and some are odd, divide all the even numbers by 2.
        if (numEven > 0 && numOdd > 0)
        {
            for (int i = 0; i < nargs; i++)
            {
                if (terms[i] == 0)
                    continue;

                if ((terms[i] & 1)  == 0) 
                    terms[i] >>= 1;
            }
        }

        //If every number in S is odd, then choose an arbitrary element of S and call it k.
        //Replace every other element, say n, with | n−k | / 2.
        if (numEven == 0)
        {
            for (int i = 0; i < nargs; i++)
            {
                if (i == smallindex || terms[i] == 0)
                    continue;

                terms[i] = abs(terms[i] - terms[smallindex]) >> 1;
            }
        }

    } while (numEven + numOdd > 1);

    // only one remaining element multiply the final answer by 2s at the end.
    for (int i = 0; i < nargs; i++)
    {
        if (terms[i] == 0)
            continue;

        return terms[i] << shift;
    }
    return 0;
};

Answer 6

Para golang, usando el resto

func GetGCD(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func GetGCDFromList(numbers []int) int {
    var gdc = numbers[0]
    for i := 1; i < len(numbers); i++ {
        number := numbers[i]
        gdc  = GetGCD(gdc, number)
    }
    return gdc
}