Eukleidese algoritm: GCD (suurim ühine jagaja), selgitatud C ++ ja Java näidetega

Selle teema jaoks peate kõigepealt teadma suurima ühisjaguri (GCD) ja MOD-i toimingut.

Suurim ühine jagaja (GCD)

Kahe või enama täisarvu GCD on suurim täisarv, mis jagab kõik täisarvud nii, et nende ülejäänud osa oleks null.

Näide

GCD 20, 30 = 10   (10 on suurim arv, mis jagab 20 ja 30 ülejäänud 0-ga)

GCD 42, 120, 285 = 3   (3 on suurim arv, mis jagab 42, 120 ja 285 ülejäänud 0-ga)

"mod" operatsioon

Mod-toiming annab teile ülejäänud, kui kaks positiivset täisarvu jagatakse. Me kirjutame selle järgmiselt

A mod B = R

See tähendab, et jagades A B-ga, saate ülejäänud R, see erineb teie jagamistoimingust, mis annab teile jagatise.

Näide

7 mod 2 = 1   (jagades 7 kahega, saate ülejäänud 1)

42 mod 7 = 0   (jagades 42 7-ga, saate ülejäänud 0)

Kahe ülalnimetatud mõistega saate hõlpsasti aru Eukleidese algoritmist.

Eukleidese algoritm suurima ühisjaguri (GCD) jaoks

Eukleidese algoritm leiab kahe numbri GCD.

Sellest algoritmist saate paremini aru, kui näete seda toimimas. Eeldades, et soovite arvutada GCD 1220 ja 516, võimaldab rakendada Eukleidese algoritmi

Eeldades, et soovite arvutada GCD 1220 ja 516, võimaldab rakendada Eukleidese algoritmi

Eukleidese näide

Algoritmi pseudokood -

1. samm:   olgu   a, b  kaks numbrit

2. samm:  a mod b = R

3. samm:   laske   a = b  ja  b = R

4. samm:   korrake 2. ja 3. toimingut, kuni see   a mod b  on suurem kui 0

5. samm:   GCD = b

6. samm: lõpetage

JavaScripti kood GCD teostamiseks

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

JavaScripti kood GCD teostamiseks rekursiooni abil

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

C-kood GCD teostamiseks rekursiooni abil

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 ++ kood GCD teostamiseks

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

Pythoni kood GCD teostamiseks rekursiooni abil

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

Java kood GCD teostamiseks rekursiooni abil

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

Rohkem kui kahest numbrist koosneva GCD leidmiseks võite kasutada ka Eukleidese algoritmi. Kuna GCD on assotsiatiivne, kehtib järgmine toiming -  GCD(a,b,c) == GCD(GCD(a,b), c)

Arvutage kahe esimese numbri GCD, seejärel leidke tulemuse ja järgmise arvu GCD. Näide  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

n  Samamoodi leiate numbrite GCD   .

Mis on laiendatud eukleidiline algoritm?

See on Eukleidese algoritmi laiendus. See arvutab ka koefitsiendid x, y nii, et

ax + poolt = gcd (a, b)

x ja y on tuntud ka kui Bézouti identiteedi koefitsiendid.

laiendatud eukleidese algoritmi c-kood

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