두 개 이상의 숫자에 대한 유클리드 최대 공약수

Question

두 개 이상의 숫자에 대해 최대 공약수 알고리즘을 찾는 예를 보여줄 수 있습니까?

저는 프로그래밍 언어가 중요하지 않다고 생각합니다.

Answer 1

첫 번째 쌍부터 시작하여 GCD를 얻은 다음 그 결과와 다음 번호의 GCD를 가져옵니다. 분명한 최적화는 실행중인 GCD가 1에 도달하면 멈출 수 있다는 것입니다. 다른 최적화가 있는지 보려면이 것을보아야합니다. :)

오, 그리고 이것은 조작이 교환 적이거나 결합 적이기 때문에 쉽게 병렬화 될 수 있습니다.

Answer 2

3 자리 숫자의 GCD는 gcd(a, b, c) = gcd(gcd(a, b), c)으로 계산할 수 있습니다. 유클리드 알고리즘, 확장 유클리드 또는 이진 GCD 알고리즘을 반복적으로 적용하여 답을 얻을 수 있습니다. 나는 불행하게도 GCD를 찾는 다른 어떤 (똑똑한) 방법을 알고 있지 않습니다. (최적되지 않음) 자바에서

Answer 3

: 난 그냥이에 위키 페이지를 업데이트

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

늦게 알고리즘의 샘 하웰의 설명을 활용하여 내가 알고있는 자,하지만, 간단한 자바 스크립트 구현에 약간의 다음 동안 golang를 들어

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

를 사용하여 나머지

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 
}