Euclidean наибольший общий делитель для более чем двух чисел

Question

Может ли кто-нибудь дать пример для нахождения наиболее распространенного алгоритма делителя для более чем двух чисел?

Я считаю, что язык программирования не имеет значения.

Answer 1

Начните с первой пары и получите их GCD, затем возьмите GCD этого результата и следующее число. Очевидная оптимизация заключается в том, что вы можете остановиться, если работающий GCD когда-либо достигнет 1. Я смотрю этот, чтобы увидеть, есть ли какие-либо другие оптимизации. :)

О, и это можно легко распараллелить, так как операции являются коммутативными/ассоциативными.

Answer 2

GCD из 3 чисел можно вычислить как gcd(a, b, c) = gcd(gcd(a, b), c). Вы можете применить алгоритм Евклида, расширенный евклидово или бинарный алгоритм GCD итеративно и получить ответ. К сожалению, я не знаю о других (более умных?) Способах найти GCD.

Answer 3

В Java (не оптимальной):

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

Я только что обновил страницу вики на этом.

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

Это занимает произвольное число слагаемых. использование 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

Немного опоздал на вечеринку, я знаю, но простой реализации JavaScript, используя описание Сэма Харуэлле по алгоритму:

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

Для golang, используя остаточный

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 
}