Величайший общий делитель из набора из более чем 2 целых чисел

Question

Существует несколько вопросов о переполнении стека, в которых обсуждается, как найти наибольший общий делитель двух значений.Один хороший ответ показывает аккуратную рекурсивную функцию для этого.

Но как мне найти GCD из набора из более чем 2 целых чисел?Я не могу найти пример этого.

---

Может кто-нибудь предложить наиболее эффективный код для реализации этой функции?

static int GCD(int[] IntegerSet)
{
    // what goes here?
}

Answer 1

А здесь у вас есть пример кода с использованием метода LINQ и GCD из вопроса, который вы связали.Он использует теоретический алгоритм, описанный в других ответах ... GCD(a, b, c) = GCD(GCD(a, b), c)

static int GCD(int[] numbers)
{
    return numbers.Aggregate(GCD);
}

static int GCD(int a, int b)
{
    return b == 0 ? a : GCD(b, a % b);
}

Answer 2

Вы можете использовать это общее свойство GCD:

GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b)

Если вы уже определили GCD(a, b), его легко обобщить:

public class Program
{
    static void Main()
    {
        Console.WriteLine(GCD(new[] { 10, 15, 30, 45 }));
    }

    static int GCD(int a, int b)
    {
        return b == 0 ? a : GCD(b, a % b);
    }

    static int GCD(int[] integerSet)
    {
        return integerSet.Aggregate(GCD);
    }    
}

Answer 3

Вот версия C #.

  public static int Gcd(int[] x) {
      if (x.length < 2) {
          throw new ArgumentException("Do not use this method if there are less than two numbers.");
      }
      int tmp = Gcd(x[x.length - 1], x[x.length - 2]);
      for (int i = x.length - 3; i >= 0; i--) {
          if (x[i] < 0) {
              throw new ArgumentException("Cannot compute the least common multiple of several numbers where one, at least, is negative.");
          }
          tmp = Gcd(tmp, x[i]);
      }
      return tmp;
  }

  public static int Gcd(int x1, int x2) {
      if (x1 < 0 || x2 < 0) {
          throw new ArgumentException("Cannot compute the GCD if one integer is negative.");
      }
      int a, b, g, z;

      if (x1 > x2) {
          a = x1;
          b = x2;
      } else {
          a = x2;
          b = x1;
      }

      if (b == 0) return 0;

      g = b;
      while (g != 0) {
          z= a % g;
          a = g;
          g = z;
      }
      return a;
  }

}

Источник http://www.java2s.com/Tutorial/Java/0120__Development/GreatestCommonDivisorGCDofpositiveintegernumbers.htm

Answer 4

Википедия :

gcd является ассоциативной функцией: gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).

Gcd из трех чисел может быть вычислено как gcd (a, b, c) = gcd (gcd (a, b), c) или каким-либо другим способом, применяя коммутативность и ассоциативность.Это может быть расширено до любого числа чисел.

Просто возьмите gcd первых двух элементов, затем вычислите gcd результата и третьего элемента, затем вычислите gcd результата и четвертогоэлемент ...

Answer 5

Переписать это как одну функцию ...

    static int GCD(params int[] numbers)
    {
        Func<int, int, int> gcd = null;
        gcd = (a, b) => (b == 0 ? a : gcd(b, a % b));
        return numbers.Aggregate(gcd);
    } 

Answer 6

int GCD(int a,int b){ 
    return (!b) ? (a) : GCD(b, a%b);
}

void calc(a){
    int gcd = a[0];
    for(int i = 1 ; i < n;i++){
        if(gcd == 1){
            break;
        }
        gcd = GCD(gcd,a[i]);
    }
}

Answer 7

gcd(a1,a2,...,an)=gcd(a1,gcd(a2,gcd(a3...(gcd(a(n-1),an))))), так что я бы сделал это просто шаг за шагом, прерывая, если некоторые gcd оцениваются как 1.

Если ваш массив отсортирован, может быть быстрее вычислить gcd для небольших чиселранее, с тех пор может быть более вероятно, что один gcd оценивается как 1, и вы можете остановиться.

Answer 8

Используя это, вы также можете передавать несколько значений в виде массива: -

// pass all the values in array and call findGCD function
    int findGCD(int arr[], int n) 
    { 
        int gcd = arr[0]; 
        for (int i = 1; i < n; i++) {
            gcd = getGcd(arr[i], gcd); 
}

        return gcd; 
    } 

// check for gcd
int getGcd(int x, int y) 
    { 
        if (x == 0) 
            return y; 
        return gcd(y % x, x); 
    } 

Answer 9

GCD (a, b, c) = GCD (а, GCD (b, c)) = GCD (GCD (a, b), c) = GCD (GCD (a, c), b)

enter code here

открытый класс Program {static void Main () {Console.WriteLine (GCD (new [] {10, 15, 30, 45}));} static int GCD (int a, int b) {return b == 0?а: GCD (б, а% б);} static int GCD (int [] integerSet) {return integerSet.Aggregate (GCD);}}

Answer 10

let a = 3
let b = 9

func gcd(a:Int, b:Int) -> Int {
    if a == b {
        return a
    }
    else {
        if a > b {
            return gcd(a:a-b,b:b)
        }
        else {
            return gcd(a:a,b:b-a)
        }
    }
}
print(gcd(a:a, b:b))