Euklidischer Algorithmus: GCD (Greatest Common Divisor) Erklärt mit C ++ - und Java-Beispielen

Für dieses Thema müssen Sie zuerst den Greatest Common Divisor (GCD) und die MOD-Operation kennen.

Größter gemeinsamer Teiler (GCD)

Die GCD von zwei oder mehr Ganzzahlen ist die größte Ganzzahl, die jede der Ganzzahlen so teilt, dass ihr Rest Null ist.

Beispiel-

GCD von 20, 30 = 10   (10 ist die größte Zahl, die 20 und 30 mit dem Rest als 0 teilt)

GCD von 42, 120, 285 = 3   (3 ist die größte Zahl, die 42, 120 und 285 mit dem Rest als 0 teilt)

"mod" Betrieb

Die Mod-Operation gibt Ihnen den Rest, wenn zwei positive ganze Zahlen geteilt werden. Wir schreiben es wie folgt:

A mod B = R

Das heißt, wenn Sie A durch B teilen, erhalten Sie den Rest R. Dies unterscheidet sich von Ihrer Teilungsoperation, die Ihnen den Quotienten ergibt.

Beispiel-

7 mod 2 = 1   (Teilen von 7 durch 2 ergibt den Rest 1)

42 mod 7 = 0   (Teilen von 42 durch 7 ergibt den Rest 0)

Wenn Sie die beiden oben genannten Konzepte verstanden haben, werden Sie den euklidischen Algorithmus leicht verstehen.

Euklidischer Algorithmus für den größten gemeinsamen Teiler (GCD)

Der euklidische Algorithmus findet die GCD von 2 Zahlen.

Sie werden diesen Algorithmus besser verstehen, wenn Sie ihn in Aktion sehen. Angenommen, Sie möchten die GCD von 1220 und 516 berechnen, wenden wir den euklidischen Algorithmus an.

Angenommen, Sie möchten die GCD von 1220 und 516 berechnen, wenden wir den euklidischen Algorithmus an.

Euklidisches Beispiel

Pseudocode des Algorithmus-

Schritt 1:   Sei   a, b  die zwei Zahlen

Schritt 2:  a mod b = R

Schritt 3:   Lassen Sie   a = b  und  b = R

Schritt 4:   Wiederholen Sie die Schritte 2 und 3, bis sie   a mod b  größer als 0 sind

Schritt 5:   GCD = b

Schritt 6: Beenden

JavaScript-Code zur Durchführung von GCD-

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

JavaScript-Code zur Durchführung von GCD mit Rekursion-

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

C-Code zur Durchführung der GCD mithilfe der 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 ++ Code zur Durchführung von GCD-

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

Python-Code zur Durchführung der GCD mithilfe der Rekursion

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

Java-Code zur Durchführung der GCD mithilfe der Rekursion

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

Sie können auch den euklidischen Algorithmus verwenden, um GCD mit mehr als zwei Zahlen zu finden. Da GCD assoziativ ist, ist die folgende Operation gültig:  GCD(a,b,c) == GCD(GCD(a,b), c)

Berechnen Sie die GCD der ersten beiden Zahlen und ermitteln Sie dann die GCD des Ergebnisses und der nächsten Zahl. Beispiel-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Sie können GCD von   n  Zahlen auf die gleiche Weise finden.

Was ist der erweiterte euklidische Algorithmus?

Dies ist eine Erweiterung des euklidischen Algorithmus. Es berechnet auch die Koeffizienten x, y so, dass

ax + by = gcd (a, b)

x und y sind auch als Koeffizienten der Identität von Bézout bekannt.

c-Code für den erweiterten euklidischen Algorithmus

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