Euklidov algoritam: GCD (najveći zajednički djelitelj) objašnjen na primjerima C ++ i Java

Za ovu temu prvo morate znati o Najvećem zajedničkom djelitelju (GCD) i radu MORH-a.

Najveći zajednički djelitelj (GCD)

GCD od dvije ili više cijelih brojeva najveći je cijeli broj koji dijeli svaki od cijelih brojeva tako da je njihov ostatak jednak nuli.

Primjer-

GCD od 20, 30 = 10   (10 je najveći broj koji dijeli 20 i 30 s ostatkom kao 0)

GCD od 42, 120, 285 = 3   (3 je najveći broj koji dijeli 42, 120 i 285 s ostatkom kao 0)

"mod" rad

Mod operacija daje vam ostatak kada se podijele dvije pozitivne cijele vrijednosti. Mi to zapisujemo na sljedeći način-

A mod B = R

To znači da dijeljenjem A s B dobivate ostatak R, ovo je drugačije od vašeg dijeljenja koje vam daje količnik.

Primjer-

7 mod 2 = 1   (Podjelom 7 s 2 dobiva se ostatak 1)

42 mod 7 = 0   (Dijeljenje 42 sa 7 daje ostatak 0)

Uz gornja dva shvaćena pojma lako ćete razumjeti euklidski algoritam.

Euklidov algoritam za najveći zajednički djelitelj (GCD)

Euklidov algoritam pronalazi GCD od 2 broja.

Ovaj ćete algoritam bolje razumjeti ako ga vidite na djelu. Pod pretpostavkom da želite izračunati GCD 1220 i 516, dopustimo primjenu Euklidovog algoritma -

Pod pretpostavkom da želite izračunati GCD 1220 i 516, dopustimo primjenu Euklidovog algoritma -

Euklidski primjer

Pseudo kôd algoritma-

Korak 1:   Neka   a, b  budu dva broja

Korak 2:  a mod b = R

Korak 3:   Neka   a = b  i  b = R

Korak 4:   Ponavljajte korake 2 i 3 dok ne   a mod b  bude veće od 0

Korak 5:   GCD = b

Korak 6: Završi

JavaScript kôd za izvođenje GCD-

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

JavaScript kôd za izvođenje GCD-a pomoću rekurzije-

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

C kod za izvođenje GCD-a pomoću rekurzije

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

C ++ kôd za izvođenje GCD-

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

Python kod za izvođenje GCD-a pomoću rekurzije

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

Java kôd za izvođenje GCD-a pomoću rekurzije

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

Također možete koristiti Euklidov algoritam da biste pronašli GCD više od dva broja. Budući da je GCD asocijativan, vrijedi sljedeća operacija -  GCD(a,b,c) == GCD(GCD(a,b), c)

Izračunajte GCD prva dva broja, a zatim pronađite GCD rezultata i sljedeći broj. Primjer-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

GCD n  brojeva možete pronaći   na isti način.

Što je Prošireni Euklidov algoritam?

Ovo je proširenje euklidskog algoritma. Također izračunava koeficijente x, y tako da

ax + by = gcd (a, b)

x i y poznati su i kao koeficijenti Bézoutova identiteta.

c kôd za Prošireni Euklidov algoritam

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