Euklidesowy największy wspólny dzielnik dla więcej niż dwóch liczb

Question

Czy ktoś może podać przykład znajdowania największego wspólnego algorytmu dzielnika dla więcej niż dwóch liczb?

Uważam, że język programowania nie ma znaczenia.

Answer 1

Zacznij od pierwszej pary i pobierz ich GCD, a następnie pobierz GCD tego wyniku i następnego numeru. Oczywistą optymalizację można zatrzymać, jeśli działający GCD osiągnie 1. Oglądam ten, aby zobaczyć, czy są jakieś inne optymalizacje. :)

Och, a to może być łatwo zrównoleglone, ponieważ operacje są przemienne/asocjacyjne.

Answer 2

GCD z 3 cyframi można obliczyć jako gcd(a, b, c) = gcd(gcd(a, b), c). Możesz iteracyjnie zastosować algorytm Euklidesa, rozszerzony Euklidesowy lub binarny algorytm GCD i uzyskać odpowiedź. Nie jestem świadomy żadnych innych (mądrzejszy?) Sposobów, aby znaleźć GCD, niestety.

Answer 3

W Javie (nie optymalne):

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

Właśnie aktualizowane strony Wiki na ten temat.

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

Dzieje dowolną liczbę składników. użyj 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

Trochę późno na imprezę wiem, ale prostego wdrożenia JavaScript, wykorzystując opis Sam Harwell za algorytmu:

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

Dla golang, z wykorzystaniem resztkowej

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 
}