Euklidisk algoritme: GCD (Greatest Common Divisor) forklaret med C ++ og Java eksempler

Til dette emne skal du først vide om Greatest Common Divisor (GCD) og MOD-operationen.

Greatest Common Divisor (GCD)

GCD på to eller flere heltal er det største heltal, der deler hvert af de helt tal, så deres resterende er nul.

Eksempel-

GCD på 20, 30 = 10   (10 er det største tal, der deler 20 og 30 med resten som 0)

GCD på 42, ​​120, 285 = 3   (3 er det største tal, der deler 42, 120 og 285 med resten som 0)

"mod" Operation

Mod-operationen giver dig resten, når to positive heltal er opdelt. Vi skriver det som følger-

A mod B = R

Det betyder, at dividere A med B giver dig resten R, dette er anderledes end din divisionsoperation, som giver dig kvotienten.

Eksempel-

7 mod 2 = 1   (At dividere 7 med 2 giver resten 1)

42 mod 7 = 0   (Opdeling 42 af 7 giver resten 0)

Med de to ovenstående begreber forstået vil du let forstå den euklidiske algoritme.

Euklidisk algoritme for den største fælles skiller (GCD)

Den euklidiske algoritme finder GCD på 2 tal.

Du vil bedre forstå denne algoritme ved at se den i aktion. Forudsat at du vil beregne GCD på 1220 og 516, kan vi anvende den euklidiske algoritme-

Forudsat at du vil beregne GCD på 1220 og 516, kan vi anvende den euklidiske algoritme-

Euklidisk eksempel

Algoritmens pseudokode-

Trin 1:   Lad   a, b  være de to tal

Trin 2:  a mod b = R

Trin 3:   Lad   a = b  og  b = R

Trin 4:   Gentag trin 2 og 3, indtil den   a mod b  er større end 0

Trin 5:   GCD = b

Trin 6: Afslut

JavaScript-kode for at udføre GCD-

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

JavaScript-kode til at udføre GCD ved hjælp af rekursions-

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

C-kode til at udføre GCD ved hjælp af rekursion

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 ++ kode til udførelse af GCD-

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

Python-kode til at udføre GCD ved hjælp af rekursion

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

Java-kode til at udføre GCD ved hjælp af rekursion

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

Du kan også bruge den euklidiske algoritme til at finde GCD på mere end to tal. Da GCD er associerende, er følgende handling gyldig-  GCD(a,b,c) == GCD(GCD(a,b), c)

Beregn GCD for de første to tal, find derefter GCD for resultatet og det næste nummer. Eksempel-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Du kan finde GCD med   n  tal på samme måde.

Hvad er den udvidede euklidiske algoritme?

Dette er en udvidelse af euklidisk algoritme. Det beregner også koefficienterne x, y sådan, at

ax + by = gcd (a, b)

x og y er også kendt som koefficienter for Bézouts identitet.

c kode for udvidet euklidisk algoritme

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