Algoritma Euclidian: GCD (Greatest Common Divisor) Dijelaskan dengan Contoh C ++ dan Java

Untuk topik ini Anda harus tahu tentang Pembagi Umum Terbesar (GCD) dan operasi MOD terlebih dahulu.

Pembagi Persekutuan Terbesar (GCD)

PBT dari dua atau lebih bilangan bulat adalah bilangan bulat terbesar yang membagi setiap bilangan bulat sehingga sisanya adalah nol.

Contoh-

PBT 20, 30 = 10   (10 adalah bilangan terbesar yang membagi 20 dan 30 dengan sisa 0)

PBK dari 42, 120, 285 = 3   (3 adalah angka terbesar yang membagi 42, 120 dan 285 dengan sisa 0)

Operasi "mod"

Operasi mod memberi Anda sisa ketika dua bilangan bulat positif dibagi. Kami menulisnya sebagai berikut-

A mod B = R

Ini berarti, membagi A dengan B menghasilkan sisa R, ini berbeda dari operasi pembagian Anda yang memberi Anda hasil bagi.

Contoh-

7 mod 2 = 1   (Membagi 7 dengan 2 menghasilkan sisa 1)

42 mod 7 = 0   (Membagi 42 dengan 7 menghasilkan sisa 0)

Dengan memahami kedua konsep di atas maka Anda akan dengan mudah memahami Algoritma Euclidean.

Algoritma Euclidean for Greatest Common Divisor (GCD)

Algoritma Euclidean menemukan GCD dari 2 angka.

Anda akan lebih memahami Algoritma ini dengan melihatnya beraksi. Dengan asumsi Anda ingin menghitung PBT 1220 dan 516, mari terapkan Algoritma Euclidean-

Dengan asumsi Anda ingin menghitung PBT 1220 dan 516, mari terapkan Algoritma Euclidean-

Contoh Euclidean

Kode Pseudo dari Algoritma-

Langkah 1:   Membiarkan   a, b  menjadi dua angka

Langkah 2:  a mod b = R

Langkah 3:   Biarkan   a = b  dan  b = R

Langkah 4:   Ulangi Langkah 2 dan 3 hingga   a mod b  lebih besar dari 0

Langkah 5:   GCD = b

Langkah 6: Selesai

Kode JavaScript untuk Melakukan GCD-

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

Kode JavaScript untuk Melakukan GCD menggunakan Rekursi-

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

Kode C untuk melakukan GCD menggunakan rekursi

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

Kode C ++ untuk Melakukan GCD-

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

Kode Python untuk Melakukan GCD menggunakan Rekursi

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

Kode Java untuk Melakukan GCD menggunakan Rekursi

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

Anda juga dapat menggunakan Algoritma Euclidean untuk menemukan GCD lebih dari dua angka. Karena, GCD adalah asosiatif, operasi berikut ini valid-  GCD(a,b,c) == GCD(GCD(a,b), c)

Hitung PBT dari dua angka pertama, lalu cari PBT hasil dan angka berikutnya. Contoh-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Anda dapat menemukan GCD   n  angka dengan cara yang sama.

Apa itu Algoritma Euclidean yang Diperluas?

Ini adalah perpanjangan dari algoritma Euclidean. Itu juga menghitung koefisien x, y sedemikian rupa

ax + by = gcd (a, b)

x dan y juga dikenal sebagai koefisien identitas B├ęzout.

kode c untuk algoritma Extended Euclidean

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