divisor común más grande euclidiano para más de dos números

Question

¿Alguien puede dar un ejemplo para encontrar el mayor algoritmo de 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 GCD, luego tome el GCD de ese resultado y el siguiente número. La optimización obvia es que puede detenerse si el GCD en ejecución alcanza alguna vez 1. Estoy viendo este para ver si hay otras optimizaciones. :)

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

Answer 2

El GCD de 3 números se puede calcular como gcd(a, b, c) = gcd(gcd(a, b), c). Puede aplicar el algoritmo euclidiano, el euclidiano extendido o el algoritmo binario GCD de forma iterativa y obtener su respuesta. No estoy al tanto de ninguna otra forma (más inteligente) de encontrar un GCD, desafortunadamente.

Answer 3

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 4

Acabo de actualizar una página wiki en esta.

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

Esto toma un número arbitrario de términos. usan 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 5

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

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 6

Para golang, usando 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 
}