Algoritmo euclideo: GCD (Greatest Common Divisor) spiegato con esempi in C ++ e Java

Per questo argomento è necessario prima conoscere il Greatest Common Divisor (GCD) e l'operazione MOD.

Greatest Common Divisor (GCD)

Il GCD di due o più numeri interi è il numero intero più grande che divide ciascuno degli interi in modo che il loro resto sia zero.

Esempio-

MCD di 20, 30 = 10   (10 è il numero più grande che divide 20 e 30 con il resto come 0)

MCD di 42, 120, 285 = 3   (3 è il numero più grande che divide 42, 120 e 285 con il resto come 0)

Operazione "mod"

L'operazione mod ti dà il resto quando vengono divisi due numeri interi positivi. Lo scriviamo come segue-

A mod B = R

Ciò significa che dividendo A per B ottieni il resto R, questo è diverso dalla tua operazione di divisione che ti dà il quoziente.

Esempio-

7 mod 2 = 1   (dividendo 7 per 2 si ottiene il resto 1)

42 mod 7 = 0   (dividendo 42 per 7 si ottiene il resto 0)

Con i due concetti precedenti compresi, comprenderai facilmente l'algoritmo euclideo.

Algoritmo euclideo per il più grande divisore comune (GCD)

L'algoritmo euclideo trova il GCD di 2 numeri.

Capirai meglio questo algoritmo vedendolo in azione. Supponendo che tu voglia calcolare il MCD di 1220 e 516, applichiamo l'algoritmo euclideo-

Supponendo che tu voglia calcolare il MCD di 1220 e 516, applichiamo l'algoritmo euclideo-

Esempio euclideo

Pseudo codice dell'algoritmo

Fase 1:   Lasciate   a, b  essere i due numeri

Passo 2:  a mod b = R

Passaggio 3:   lascia   a = b  e  b = R

Passaggio 4:   ripetere i passaggi 2 e 3 finché non   a mod b  è maggiore di 0

Passaggio 5:   GCD = b

Passaggio 6: Fine

Codice JavaScript per eseguire GCD

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

Codice JavaScript per eseguire GCD utilizzando la ricorsione-

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

Codice C per eseguire GCD utilizzando la ricorsione

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

Codice C ++ per eseguire GCD-

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

Codice Python per eseguire GCD utilizzando la ricorsione

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

Codice Java per eseguire GCD utilizzando la ricorsione

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

Puoi anche usare l'algoritmo euclideo per trovare MCD di più di due numeri. Poiché GCD è associativo, è valida la seguente operazione:  GCD(a,b,c) == GCD(GCD(a,b), c)

Calcola il MCD dei primi due numeri, quindi trova il MCD del risultato e il numero successivo. Esempio-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Puoi trovare il GCD dei   n  numeri allo stesso modo.

Cos'è l'algoritmo euclideo esteso?

Questa è un'estensione dell'algoritmo euclideo. Calcola anche i coefficienti x, y tali che

ax + by = mcd (a, b)

xey sono anche conosciuti come coefficienti dell'identità di Bézout.

codice c per algoritmo euclideo esteso

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