1 Востаннє редагувалося FakiNyan (08.11.2021 21:33:48)

Тема: Чому пошук найбільшого спільного дільника працює?

Вітаю.
Знайшов такий код

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

Перевірив на папері, і бачу, шо працює, але не до кінця розумію, яка за цим логіка стоїть.

Наприклад, маємо 18 та 4. Той метод пошуку найбільшого дільника, який я розумію, це розклад чисел на множники, і пошук найбільшого спільного множника.

18 = 2 * 3 * 3
4 = 2 * 2

Найбільший спільний множник = 2, і воно й буде найбільшим спільним дільником для двох чисел. (я можу заплутатись в термінах трохи, але то таке).

Але код використовує ділення по модулю, тобто, воно повертає залишок від ділення.

18 % 4 = 2, бо 16 ділиться на 4, і залишається лише 2.

Далі йде 4 % 2 = 0, тобто, ми дійшли до кінця, і найбільшим спільним дільником є 2. Але чого воно працює?
**************************************

Поки що я розуміє наступне.

По-перше, якщо b % a = 0, то тут очевидно, що a є найбільшим спільним дільником, тому що воно ділиться на b, і саме на себе, якщо b < a, то % поверне b, котре =/= 0, і далі a та b міняються місцями.

Якщо b % a =/= 0, то це означає, що найбільший спільний дільник десь між 1 (включно) та a (не включно), і далі a - це залишок від ділення (котрий менший a), а b - це старе a (котре більше за залишок), і тепер ми намагаємось знайти найбільший спільний дільник між старим a, та залишок від ділення, котрий менший a.
***************************************

Чому в якості нового a ми використовуємо залишок від ділення, а в якості нового b - старе a ?

2

Re: Чому пошук найбільшого спільного дільника працює?

https://uk.wikipedia.org/wiki/Алгоритм_Евкліда

Подякували: FakiNyan, leofun012

3

Re: Чому пошук найбільшого спільного дільника працює?

Чесно кажучи, сама ота статя мені геть не допомогла, але коли я то почав гуглити, то надибав файне відео, де то всьо показують візуально.

Там ідея в тому, що якщо отой найбільший дільник існує, а він може бути 1, або більше 1. Тоді обидва числа можна розбити на дві множини, складові цих множин будуть саме отим найбільшим дільником. Тобто,
18 та 4 можуть бути як
1 * 18 та 1 * 4
або
2 * 9 та 2 * 2, тобто у нас є дев'ять двійок, та дві двійки. 18 % 4 знаходить у дев'яти двійках всі комбінації з двох двійок, та віднімає їх, і у нас залишається лише одна двійка, потім ми дивимось на 4, котра складається з двох двійок, та віднімаємо з неї всі двійки, і т.д. І от коли одна зі сторін вже нічого не має, то те, що залишилось, і є найбільшим спільним дільником.
https://replace.org.ua/uploads/images/2564/a8534e2a19c6531432c3e210ff4b655d.png
Тобто, ми по суті нічого не "обраховуємо", а просто "знімаємо зайве", поки не дійдемо до самого ядра, котре вже не можна далі роздягнути.