AlgorithmO #10 - Двоичен алгоритъм за НОД (+ намиране на НОК)

Днешният алгоритъм не е нищо специално, а просто още един начин по който можем да намерим най-голям общ делител (НОД) на 2 числа. Предимството му пред алгоритъма на Евклид е, че обикновено се представя по-добре при реални тестове. Имплементацията му е малко по-объркваща, но не е нищо особено като цяло.

За да не бъде изключително скучен този пост, ще ви спомена как да намерим и НОК (най-малко общо кратно - т.е., най-малкото число, което се дели на няколко други числа и е тяхно "кратно"). 😉

---

Кой не обича math jokes... :)

ОПИСАНИЕ:

Двоичният алгоритъм за намиране на НОД (понякога наричан Stein's algorithm - алгоритъм на Стайн, Стейн, Щайн... кой знае?) използва набор от правила, с които намалява изчисленията по намирането на НОД.

Ще отбележим 2-те числа, на които търсим НОД, с 'u' и 'v'.

Алгоритъмът изисква време пропорционално на квадрата на общия брой на битове, които 'u' и 'v' заемат. Въпреки че поне едно от числата се редуцира на всяка стъпка, изваждането и преместването не се извършват за константно време всеки път (особено за много големи числа) , но все пак на практика те са доста бързи операции.

(последният параграф взет от дадените ми лекции по Проектиране и анализ на алгоритми :))

АЛГОРИТЪМ:

НОД (u, v) = ?

1) НОД(0, v) = v
2) НОД(u, 0) = u

* НОД(0, 0) е неопределен.

3) u, v - четни
-> НОД(u,v) = 2 * НОД (u/2, v/2)

4) u - четно, v - нечетно

-> НОД(u,v) = НОД(u/2, v)

5) u - нечетно, v - четно
-> НОД(u,v) = НОД(u, v/2)

6) u, v - нечетни
- u >= v
-> НОД(u,v) = НОД( (u-v)/2, v )
- v > u
-> НОД(u,v) = НОД( u, (v-u)/2 )

Намиране на НОК (бонус алгоритъм):

Намирането на НОК става изключително лесно след като знаем НОД на 2-те числа. Прилагаме формулата:

НОК(a, b) = (a * b) / НОД(a, b)

За повече от 2 числа, прилагаме НОК(a, b, c) = НОК(а, НОК(b, c)).

ПРИМЕР:

Ето няколко примера, които илюстрират как точно се прилага двоичният алгоритъм на всяка стъпка.

Смятам, че няма нужда от обяснения този път. 😄

===

НОД(728, 140) =
= 2 * НОД(364, 70) =
= 2 * 2 * НОД(182, 35) =
= 2 * 2 * НОД(91, 35) =
= 2 * 2 * НОД( (91-35)/2, 35 ) =
= 2 * 2 * НОД(56/2, 35)
= 2 * 2 * НОД(28, 35) =
= 2 * 2 * НОД(28/2, 35) =
= 2 * 2 * НОД(14, 35) =
= 2 * 2 * НОД(14/2, 35) =
= 2 * 2 * НОД(7, 35) =
= 2 * 2 * НОД( 7, (35-7)/2 ) =
= 2 * 2 * НОД(7, 28/2) =
= 2 * 2 * НОД(7, 14) =
= 2 * 2 * НОД(7, 14/2) =
= 2 * 2 * НОД(7, 7) =
= 2 * 2 * НОД( (7-7)/2, 7) ) =
= 2 * 2 * НОД(0, 7) =
= 2 * 2 * 7 =
= 28

===

НОД(2505, 9775) =
= НОД( 2505, (9775-2505)/2 ) =
= НОД(2505, 7270/2)
= НОД(2505, 3635)
= НОД( 2505, (3635-2505)/2 ) =
= НОД(2505, 1130/2) =
= НОД(2505, 565)
= НОД( (2505-565)/2, 565) =
= НОД(1940/2, 565) =
= НОД(970, 565) =
= НОД(970/2, 565) =
= НОД(485, 565) =
= НОД( 485, (565-485)/2) ) =
= НОД(485, 80/2) =
= НОД(485, 40) =
= НОД(485, 40/2) =
= НОД(485, 20) =
= НОД(485, 20/2) =
= НОД(485, 10) =
= НОД(485, 10/2) =
= НОД(485, 5) =
= НОД( (485-5)/2, 5 ) =
= НОД(480/2, 5) =
= НОД(240, 5) =
= НОД(240/2, 5) =
= НОД(120, 5) =
= НОД(120/2, 5) =
= НОД(60, 5) =
= НОД(60/2, 5) =
= НОД(30, 5) =
= НОД(30/2, 5) =
= НОД(15, 5) =
= НОД( (15-5)/2, 5) =
= НОД(10/2, 5) =
= НОД(5, 5) =
= НОД( (5-5)/2, 5 ) =
= НОД(0, 5) =
= 5

===

НОД(10127, 8323) =
= НОД( (10127-8323)/2, 8323 ) =
= НОД(1804/2, 8323) =
= НОД(902, 8323) =
= НОД(902/2, 8323) =
= НОД(451, 8323) =
= НОД( 451, (8323-451)/2 ) =
= НОД(451, 7872/2) =
= НОД(451, 3936) =
= НОД(451, 3936/2) =
= НОД(451, 1968) =
= НОД(451, 1968/2) =
= НОД(451, 984) =
= НОД(451, 984/2) =
= НОД(451, 492) =
= НОД(451, 492/2) =
= НОД(451, 246) =
= НОД(451, 246/2) =
= НОД(451, 123) =
= НОД( (451-123)/2, 123 ) =
= НОД(328/2, 123) =
= НОД(164, 123) =
= НОД(164/2, 123) =
= НОД(82, 123) =
= НОД(82/2, 123) =
= НОД(41, 123) =
= НОД( 41, (123-41)/2 ) =
= НОД(41, 82/2) =
= НОД(41, 41) =
= НОД( (41-41)/2, 41 ) =
= НОД(0, 41) =
= 41

ИМПЛЕМЕНТАЦИЯ (Java):

	public class Solution {
	static int getGreatestCommonDivisor(int u, int v) {
	int greatestCommonDivisor = -1;
	/* 1.
	* - НОД(0, v) = v, тъй като 0 дели всичко, а v е най-голямото число, което дели v.
	* - Aналогично, НОД(u, 0) = u.
	* - НОД(0, 0) е неопределен.
	*/
	if (u == 0) {
	greatestCommonDivisor = v;
	return greatestCommonDivisor;
	}
	else if (v == 0) {
	greatestCommonDivisor = u;
	return greatestCommonDivisor;
	}
	else if (u == 0 && v == 0) {
	return greatestCommonDivisor; // -1
	}
	/* 2.
	* - Ако u и v are са четни, НОД(u, v) = 2 * НОД(u/2, v/2), тъй като 2 е общ делител.
	*/
	else if (u % 2 == 0 && v % 2 == 0) {
	greatestCommonDivisor = 2 * getGreatestCommonDivisor(u / 2, v / 2);
	}
	/* 3.
	* - Ако u е четно, а v е нечетно, тогава, НОД(u, v) = НОД(u/2, v), тъй като 2 не е общ делител.
	* - Аналогично, ако u е нечетно, а v е четно, НОД(u, v) = НОД(u, v/2).
	*/
	else if (u % 2 == 0 && v % 2 != 0) {
	greatestCommonDivisor = getGreatestCommonDivisor(u / 2, v);
	}
	else if (u % 2 != 0 && v % 2 == 0) {
	greatestCommonDivisor = getGreatestCommonDivisor(u, v / 2);
	}
	/* 4.
	* - Ако u и v са нечетни и u ≥ v, тогава НОД(u, v) = НОД((u−v)/2, v).
	* - Ако и двете са нечетни и u < v, тогава НОД(u, v) = НОД((v-u)/2, u).
	*/
	else if (u % 2 != 0 && v % 2 != 0 && u >= v) {
	greatestCommonDivisor = getGreatestCommonDivisor((u-v)/2, v);
	return greatestCommonDivisor;
	}
	else if (u % 2 != 0 && v % 2 != 0 && u < v) {
	greatestCommonDivisor = getGreatestCommonDivisor((v-u)/2, u);
	return greatestCommonDivisor;
	}
	return greatestCommonDivisor;
	}
	public static void main(String[] args) {
	System.out.println(
	getGreatestCommonDivisor(21, 6)
	);
	}
	}

view raw ALGORITHMO-10-Binary-GCD-Algorithm-Implementation.java hosted with ❤ by GitHub

Намиране на НОК:

	public class Solution {
	static int getGreatestCommonDivisor(int a, int b) {
	while (b != 0) {
	int temp = a;
	a = b;
	b = temp % b;
	}
	int greatestCommonDivisor = a;
	return greatestCommonDivisor;
	}
	// Get LCM
	static int getLeastCommonMultiple(int a, int b) {
	int leastCommonMultiple = (a * b) / getGreatestCommonDivisor(a, b);
	return leastCommonMultiple;
	}
	public static void main(String[] args) {
	System.out.println(
	getLeastCommonMultiple(6, 21)
	);
	}
	}

view raw ALGORITHMO-10-Least-Common-Multiple-Algorithm-Implementation.java hosted with ❤ by GitHub

---

Това е за днес! Ако видите някоя грешка - сигнализирайте ми! 😉