Algorithme euclidien: GCD (Greatest Common Divisor) expliqué avec des exemples C ++ et Java

Pour cette rubrique, vous devez d'abord connaître le plus grand diviseur commun (GCD) et l'opération MOD.

Plus grand diviseur commun (GCD)

Le GCD de deux ou plusieurs entiers est le plus grand entier qui divise chacun des entiers de telle sorte que leur reste est zéro.

Exemple-

GCD de 20, 30 = 10   (10 est le plus grand nombre qui divise 20 et 30 avec le reste égal à 0)

GCD de 42, 120, 285 = 3   (3 est le plus grand nombre qui divise 42, 120 et 285 avec le reste comme 0)

Fonctionnement "mod"

L'opération mod vous donne le reste lorsque deux entiers positifs sont divisés. Nous l'écrivons comme suit -

A mod B = R

Cela signifie que diviser A par B vous donne le reste R, c'est différent de votre opération de division qui vous donne le quotient.

Exemple-

7 mod 2 = 1   (diviser 7 par 2 donne le reste 1)

42 mod 7 = 0   (diviser 42 par 7 donne le reste 0)

Avec les deux concepts ci-dessus compris, vous comprendrez facilement l'algorithme euclidien.

Algorithme euclidien pour le plus grand diviseur commun (GCD)

L'algorithme euclidien trouve le GCD de 2 nombres.

Vous comprendrez mieux cet algorithme en le voyant en action. En supposant que vous vouliez calculer le GCD de 1220 et 516, appliquons l'algorithme euclidien-

En supposant que vous vouliez calculer le GCD de 1220 et 516, appliquons l'algorithme euclidien-

Exemple euclidien

Pseudo code de l'algorithme-

Étape 1:   Soit   a, b  les deux nombres

Étape 2:  a mod b = R

Étape 3:   Laissez   a = b  et  b = R

Étape 4:   Répétez les étapes 2 et 3 jusqu'à ce qu'il   a mod b  soit supérieur à 0

Étape 5:   GCD = b

Étape 6: Terminer

Code JavaScript pour exécuter GCD-

function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } 

Code JavaScript pour exécuter GCD à l'aide de la récursivité

function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); } 

Code C pour effectuer GCD en utilisant la récursivité

int gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } 

Code C ++ pour exécuter GCD-

int gcd(int a,int b) { int R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } 

Code Python pour exécuter GCD à l'aide de la récursivité

def gcd(a, b): if b == 0: return a: else: return gcd(b, (a % b)) 

Code Java pour exécuter GCD à l'aide de la récursivité

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

Vous pouvez également utiliser l'algorithme euclidien pour trouver un GCD de plus de deux nombres. Puisque, GCD est associatif, l'opération suivante est valide:  GCD(a,b,c) == GCD(GCD(a,b), c)

Calculez le GCD des deux premiers nombres, puis trouvez le GCD du résultat et le nombre suivant. Exemple-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Vous pouvez trouver GCD de   n  nombres de la même manière.

Qu'est-ce que l'algorithme euclidien étendu?

Ceci est une extension de l'algorithme euclidien. Il calcule également les coefficients x, y tels que

ax + par = pgcd (a, b)

x et y sont également appelés coefficients d'identité de Bézout.

code c pour l'algorithme euclidien étendu

struct Triplet{ int gcd; int x; int y; }; Triplet gcdExtendedEuclid(int a,int b){ //Base Case if(b==0){ Triplet myAns; myAns.gcd = a; myAns.x = 1; myAns.y = 0; return myAns; } Triplet smallAns = gcdExtendedEuclid(b,a%b); //Extended euclid says Triplet myAns; myAns.gcd = smallAns.gcd; myAns.x = smallAns.y; myAns.y = (smallAns.x - ((a/b)*(smallAns.y))); return myAns; }