Euklidinen algoritmi: GCD (suurin yhteinen jakaja) selitetty C ++ - ja Java-esimerkeillä

Tätä aihetta varten sinun on ensin tiedettävä suurimmasta yhteisestä jakajasta (GCD) ja MOD-toiminnosta.

Suurin yhteinen jakaja (GCD)

Kahden tai useamman kokonaisluvun GCD on suurin kokonaisluku, joka jakaa jokaisen kokonaisluvun siten, että niiden loppuosa on nolla.

Esimerkki-

GCD 20, 30 = 10   (10 on suurin luku, joka jakaa 20 ja 30 lopun ollessa 0)

GCD 42, 120, 285 = 3   (3 on suurin luku, joka jakaa 42, 120 ja 285 lopun ollessa 0)

"mod" -käyttö

Mod-toiminto antaa sinulle loput, kun kaksi positiivista kokonaislukua jaetaan. Kirjoitamme sen seuraavasti-

A mod B = R

Tämä tarkoittaa, että jakamalla A: lla B: llä saat loppuosan R, tämä on erilainen kuin jakotoiminto, joka antaa sinulle osamäärän.

Esimerkki-

7 mod 2 = 1   (Jakamalla 7 kahdella saadaan loppuosa 1)

42 mod 7 = 0   (Jakamalla 42 7: llä saadaan loppuosa 0)

Edellä mainittujen kahden käsitteen avulla ymmärrät helposti euklidisen algoritmin.

Euklidinen algoritmi suurimmalle yhteiselle jakajalle (GCD)

Euklidinen algoritmi löytää kahden luvun GCD: n.

Ymmärrät tämän algoritmin paremmin näkemällä sen toiminnassa. Olettaen, että haluat laskea GCD-arvot 1220 ja 516, voidaan käyttää euklidista algoritmia

Olettaen, että haluat laskea GCD-arvot 1220 ja 516, voidaan käyttää euklidista algoritmia

Euklidinen esimerkki

Algoritmin pseudokoodi -

Vaihe 1:   Antaa   a, b  olla kaksi numeroa

Vaihe 2:  a mod b = R

Vaihe 3:   Anna   a = b  ja  b = R

Vaihe 4:   Toista vaiheet 2 ja 3, kunnes arvo   a mod b  on suurempi kuin 0

Vaihe 5:   GCD = b

Vaihe 6: Viimeistele

JavaScript-koodi GCD: n suorittamiseksi

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

JavaScript-koodi GCD: n suorittamiseksi rekursio-

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

C-koodi GCD: n suorittamiseksi rekursiota käyttämällä

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 ++ -koodi GCD-

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

Python-koodi GCD: n suorittamiseksi rekursiota käyttämällä

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

Java-koodi GCD: n suorittamiseen rekursiota käyttämällä

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

Voit myös käyttää Euklidisen algoritmia etsimään GCD, jossa on enemmän kuin kaksi numeroa. Koska GCD on assosiatiivinen, seuraava toimenpide on kelvollinen  GCD(a,b,c) == GCD(GCD(a,b), c)

Laske kahden ensimmäisen numeron GCD, etsi sitten tuloksen ja seuraavan luvun GCD. Esimerkki-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Löydät GCD-   n  numerot samalla tavalla.

Mikä on laajennettu euklidinen algoritmi?

Tämä on euklidisen algoritmin laajennus. Se laskee myös kertoimet x, y siten, että

ax + by = gcd (a, b)

x ja y tunnetaan myös Bézoutin identiteetin kertoimina.

c-koodi laajennetulle euklidiselle algoritmille

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