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

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

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

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

Ето пример:

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

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

“Mod” операция

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

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, нека приложим евклидовия алгоритъм.

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

Стъпка 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 с помощта на рекурсия:

function gcd(a, b) { if (b == 0) return a; else 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числата по същия начин.