Euklido algoritmas: GCD (didžiausias bendras daliklis), paaiškintas C ++ ir Java pavyzdžiais

Šioje temoje pirmiausia turite žinoti apie „Greatest Common Divisor“ (GCD) ir MOD operaciją.

Didžiausias bendras daliklis (GCD)

Dviejų ar daugiau sveikų skaičių GCD yra didžiausias sveikasis skaičius, kuris padalija kiekvieną iš sveikųjų skaičių taip, kad jų likutis būtų lygus nuliui.

Pavyzdys-

GCD 20, 30 = 10   (10 yra didžiausias skaičius, kuris dalija 20 ir 30, o likusi dalis yra 0)

GCD iš 42, 120, 285 = 3   (3 yra didžiausias skaičius, kuris padalija 42, 120 ir 285, o likusi dalis yra 0)

„mod“ operacija

Mod operacija suteikia jums likusią dalį, kai padalijami du teigiami sveiki skaičiai. Rašome taip:

A mod B = R

Tai reiškia, kad padaliję A iš B, gausite likusią dalį R, tai skiriasi nuo jūsų padalijimo operacijos, kuri suteikia jums koeficientą.

Pavyzdys-

7 mod 2 = 1   (padalijus 7 iš 2, gaunama likusi 1 dalis)

42 mod 7 = 0   (padalijus 42 iš 7, gaunama likusi dalis 0)

Atsižvelgdami į pirmiau pateiktas dvi suprantamas sąvokas, lengvai suprasite Euklido algoritmą.

Euklido didžiausio bendro daliklio algoritmas (GCD)

Euklido algoritmas nustato 2 skaičių GCD.

Jūs geriau suprasite šį algoritmą matydami jį veikiant. Darant prielaidą, kad norite apskaičiuoti 1220 ir 516 GCD, leidžia pritaikyti Euklido algoritmą -

Darant prielaidą, kad norite apskaičiuoti 1220 ir 516 GCD, galime pritaikyti Euklido algoritmą -

Euklido pavyzdys

Pseudo algoritmo kodas -

1 žingsnis:   Leiskite   a, b  būti du skaičiai

2 žingsnis:  a mod b = R

3 žingsnis:   Leiskite   a = b  ir  b = R

4 žingsnis:   pakartokite 2 ir 3 veiksmus, kol   a mod b  bus didesnis nei 0

5 žingsnis:   GCD = b

6 žingsnis: Baigti

„JavaScript“ kodas norint atlikti GCD-

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

„JavaScript“ kodas norint atlikti GCD naudojant rekursiją

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

C kodas norint atlikti GCD naudojant rekursiją

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 ++ kodas atlikti GCD-

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

„Python“ kodas norint atlikti GCD naudojant „Recursion“

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

„Java“ kodas norint atlikti GCD naudojant rekursiją

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

Taip pat galite naudoti Euklido algoritmą, kad rastumėte daugiau nei dviejų skaičių GCD. Kadangi GCD yra asociatyvus, ši operacija galioja  GCD(a,b,c) == GCD(GCD(a,b), c)

Apskaičiuokite pirmųjų dviejų skaičių GCD, tada raskite rezultato GCD ir kitą skaičių. Pavyzdys-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Lygiai taip pat galite rasti skaičių GCD   n  .

Kas yra išplėstinis euklido algoritmas?

Tai Euklido algoritmo išplėtimas. Jis taip pat apskaičiuoja koeficientus x, y tokius, kad

ax + pagal = gcd (a, b)

x ir y taip pat žinomi kaip Bézouto tapatybės koeficientai.

išplėstinio Euklido algoritmo c kodas

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