Евклидов алгоритъм: GCD (най-големият общ делител), обяснен с примери за C ++ и Java

За тази тема първо трябва да знаете за най-големия общ делител (GCD) и операцията на MOD.

Най-големият общ делител (GCD)

GCD от две или повече цели числа е най-голямото цяло число, което разделя всяко от целите числа така, че остатъкът им е нула.

Пример-

GCD от 20, 30 = 10   (10 е най-голямото число, което разделя 20 и 30 с остатък като 0)

GCD от 42, 120, 285 = 3   (3 е най-големият брой, който разделя 42, 120 и 285 с остатък като 0)

"мод" операция

Мод операцията ви дава остатъка, когато две положителни цели числа са разделени. Пишем го по следния начин-

A mod B = R

Това означава, че разделянето на A на B ви дава остатъка R, това е различно от операцията ви на разделяне, което ви дава коефициент.

Пример-

7 мод 2 = 1   (Разделянето на 7 на 2 дава остатъка 1)

42 mod 7 = 0   (Разделянето на 42 на 7 дава остатъка 0)

С горните две разбрани концепции лесно ще разберете евклидовия алгоритъм.

Евклидов алгоритъм за най-големия общ делител (GCD)

Евклидовият алгоритъм намира GCD от 2 числа.

Ще разберете по-добре този алгоритъм, като го видите в действие. Ако приемем, че искате да изчислите GCD от 1220 и 516, нека приложим Евклидовия алгоритъм -

Ако приемем, че искате да изчислите GCD от 1220 и 516, нека приложим евклидовия алгоритъм -

Евклидов пример

Псевдокодът на алгоритъма-

Стъпка 1:   Позволете   a, b  да бъдат двете числа

Стъпка 2:  a mod b = R

Стъпка 3:   Оставете   a = b  и  b = R

Стъпка 4:   Повторете стъпки 2 и 3, докато   a mod b  е по-голямо от 0

Стъпка 5:   GCD = b

Стъпка 6: Завършете

JavaScript код за изпълнение на GCD-

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

JavaScript код за изпълнение на GCD с помощта на Recursion-

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

C код за изпълнение на GCD с помощта на рекурсия

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 ++ код за изпълнение на GCD-

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

Python код за изпълнение на GCD с помощта на рекурсия

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

Java код за изпълнение на GCD с помощта на рекурсия

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

Можете също да използвате Евклидовия алгоритъм, за да намерите GCD от повече от две числа. Тъй като GCD е асоциативна, следната операция е валидна -  GCD(a,b,c) == GCD(GCD(a,b), c)

Изчислете GCD на първите две числа, след това намерете GCD на резултата и следващото число. Пример-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Можете да намерите GCD на   n  числата по същия начин.

Какво представлява разширеният евклидов алгоритъм?

Това е продължение на алгоритъма на Евклид. Той също така изчислява коефициентите x, y, така че

ax + by = gcd (a, b)

x и y са известни също като коефициенти на идентичността на Bézout.

c код за разширен евклидов алгоритъм

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