За тази тема първо трябва да знаете за най-големия общ делител (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; }