Евклідівський алгоритм: 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 за допомогою рекурсії-

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