Для цієї теми ви повинні знати про Найбільший загальний дільник (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 за допомогою рекурсії-
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); } Код С ++ для виконання 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 також відомі як коефіцієнти ідентичності Безу.
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; }