Plus grand diviseur commun à partir d'un ensemble de plus de 2 entiers

Question

Il y a plusieurs questions sur le dépassement de pile discutant comment trouver le plus grand commun diviseur de deux valeurs. Une bonne réponse montre un bon recursive function pour ce faire.

Mais comment puis-je trouver le GCD d'un ensemble de plus de 2 entiers? Je n'arrive pas à trouver un exemple de cela.

---

Quelqu'un peut-il suggérer le code le plus efficace pour implémenter cette fonction?

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

Answer 1

Et voici un exemple de code utilisant la méthode LINQ et GCD de la question que vous avez liée. Il utilise l'algorithme théorique décrit dans d'autres réponses ... 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

Wikipedia:

GCD est une fonction associative: pgcd (a, gcd (b, c)) = gcd (pgcd (a, b), c). Le gcd de trois nombres peut être calculé comme gcd (a, b, c) = gcd (gcd (a, b), c), ou dans certains de manière différente en appliquant la commutativité et l'associativité. Cela peut être étendu à n'importe quel nombre de nombres.

Il suffit de prendre le pgcd des deux premiers éléments, calculer alors le GCD du résultat et le troisième élément, calculer alors le GCD du résultat et quatrième élément ...

Answer 3

est ici la version 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; 
    } 

} 

Source http://www.java2s.com/Tutorial/Java/0120__Development/GreatestCommonDivisorGCDofpositiveintegernumbers.htm

Answer 4

Vous pouvez utiliser cette propriété commune d'un GCD:

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

En supposant que vous avez GCD(a, b) déjà défini, il est facile de généraliser:

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 5

gcd(a1,a2,...,an)=gcd(a1,gcd(a2,gcd(a3...(gcd(a(n-1),an))))) , donc je le ferais juste étape par étape ing si certains gcd à 1.

évalue

Si votre tableau est trié, il est peut-être plus rapide d'évaluer gcd pour un petit nombre plus tôt, car il pourrait être plus probable que l'un gcd Evalue à 1 et vous pouvez arrêter.

Answer 6

Réécriture cela comme une seule fonction ...

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 7

/* 

Copyright (c) 2011, Louis-Philippe Lessard 
All rights reserved. 

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

*/ 

unsigned gcd (unsigned a, unsigned b); 
unsigned gcd_arr(unsigned * n, unsigned size); 

int main() 
{ 
    unsigned test1[] = {8, 9, 12, 13, 39, 7, 16, 24, 26, 15}; 
    unsigned test2[] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}; 
    unsigned result; 

    result = gcd_arr(test1, sizeof(test1)/sizeof(test1[0])); 
    result = gcd_arr(test2, sizeof(test2)/sizeof(test2[0])); 

    return result; 
} 


/** 
* Find the greatest common divisor of 2 numbers 
* See http://en.wikipedia.org/wiki/Greatest_common_divisor 
* 
* @param[in] a First number 
* @param[in] b Second number 
* @return greatest common divisor 
*/ 
unsigned gcd (unsigned a, unsigned b) 
{ 
    unsigned c; 
    while (a != 0) 
    { 
     c = a; 
     a = b%a; 
     b = c; 
    } 
    return b; 
} 

/** 
* Find the greatest common divisor of an array of numbers 
* See http://en.wikipedia.org/wiki/Greatest_common_divisor 
* 
* @param[in] n Pointer to an array of number 
* @param[in] size Size of the array 
* @return greatest common divisor 
*/ 
unsigned gcd_arr(unsigned * n, unsigned size) 
{ 
    unsigned last_gcd, i; 
    if(size < 2) return 0; 

    last_gcd = gcd(n[0], n[1]); 

    for(i=2; i < size; i++) 
    { 
     last_gcd = gcd(last_gcd, n[i]); 
    } 

    return last_gcd; 
} 

Source code reference

Answer 8

Ce sont les trois plus courantes utilisé:

public static uint FindGCDModulus(uint value1, uint value2) 
{ 
    while(value1 != 0 && value2 != 0) 
    { 
      if (value1 > value2) 
      { 
        value1 %= value2; 
      } 
      else 
      { 
        value2 %= value1; 
      } 
    } 
    return Math.Max(value1, value2); 
     } 

    public static uint FindGCDEuclid(uint value1, uint value2) 
     { 
    while(value1 != 0 && value2 != 0) 
    { 
      if (value1 > value2) 
      { 
        value1 -= value2; 
      } 
      else 
      { 
        value2 -= value1; 
      } 
    } 
    return Math.Max(value1, value2); 
    } 

    public static uint FindGCDStein(uint value1, uint value2) 
    { 
    if (value1 == 0) return value2; 
    if (value2 == 0) return value1; 
    if (value1 == value2) return value1; 

    bool value1IsEven = (value1 & 1u) == 0; 
    bool value2IsEven = (value2 & 1u) == 0; 

    if (value1IsEven && value2IsEven) 
    { 
      return FindGCDStein(value1 >> 1, value2 >> 1) << 1; 
    } 
    else if (value1IsEven && !value2IsEven) 
    { 
      return FindGCDStein(value1 >> 1, value2); 
    } 
    else if (value2IsEven) 
    { 
      return FindGCDStein(value1, value2 >> 1); 
    } 
    else if (value1 > value2) 
    { 
      return FindGCDStein((value1 - value2) >> 1, value2); 
    } 
    else 
    { 
      return FindGCDStein(value1, (value2 - value1) >> 1); 
    } 
    } 

Answer 9

Sans utiliser LINQ.

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

    static int GCD(params int[] numbers) 
    { 
     int gcd = 0; 
     int a = numbers[0]; 
     for(int i = 1; i < numbers.Length; i++) 
     { 
      gcd = GCD(a, numbers[i]); 
      a = numbers[i]; 
     } 

     return gcd; 
    } 

Answer 10

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]); 
    } 
}