AlgorithmO #1 - Алгоритъм на Евклид (с изваждане)

Доста се дразня когато видя хаотични и неясни обяснения на нова важна информация. Това, което научих, е, че ако даден материал не е обяснен добре още в началото, има голям шанс изцяло да загубим интерес към дадената област.

В момента изучавам алгоритми и отново се сблъсквам с гореописания проблем. Затова ще се опитам с тази поредица от blog постове да предоставя максимално кратки и ясни обяснения на популярни алгоритми, придружени с примери, за да може всеки да разбере как точно работят и какво е приложението им.

Един трик ако искате да затвърдите знанията си в каквото и да било (или да осъзнаете къде са пропуските ви) - опитайте се да НАУЧИТЕ ДРУГ на това, което знаете.

"Ако не можеш да обясниш нещо достатъчно просто, значи не го разбираш достатъчно добре." - Алберт Айнщайн

---

Евклид след тежка вечер. :)

ОПИСАНИЕ:

Алгоритъмът на Евклид се използва за намиране на най-голям общ делител (НОД) на 2 числа. НОД представлява най-голямото число, на което и 2-те числа се делят без остатък.

Този алгоритъм се счита за един от най-старите и често се използва за опростяване на дроби или за намиране на част от решението при по-комплексни задачи.

АЛГОРИТЪМ:

НОД(A, B) = ?

1. Въведи А и B
2. Ако А != B, към стъпка 3.
    Иначе към стъпка 5.
3. Ако А > B, пресметни A = A - B.
    Иначе пресметни B = B - A
4. Kъм стъпка 2
5. Изведи А
6. Край

ПРИМЕР:

НОД(2505, 9775) = ?

A	B
2505	9775
2505	9775 - 2505 = 7270
2505	7270 - 2505 = 4765
2505	4765 - 2505 = 2260
2505 - 2260 = 245	2260
245	2260 - 245 = 2015
245	2015 - 245 = 1770
245	1770 - 245 = 1525
245	1525 - 245 = 1280
245	1280 - 245 = 1035
245	1035 - 245 = 790
245	790 - 245 = 545
245	545 - 245 = 300
245	300 - 245 = 55
245 - 55 = 190	55
190 - 55 = 135	55
135 - 55 = 80	55
80 - 55 = 25	55
25	55 - 25 = 30
25	30 - 25 = 5
25 - 5 = 20	5
20 - 5 = 15	5
15 - 5 = 10	5
10 - 5 = 5	5
5	5

=> НОД(2505, 9775) = 5

---

НОД(10127, 8323) = ?

A	B
10127	8323
10127 - 8323 = 1804	8323
1804	8323 - 1804 = 6519
1804	6519 - 1804 = 4715
1804	4715 - 1804 = 2911
1804	2911 - 1804 = 1107
1804 - 1107 = 697	1107
697	1107 - 697 = 410
697 - 410 = 287	410
287	410 - 287 = 123
287 - 123 = 164	123
164 - 123 = 41	123
41	123 - 41 = 82
41	82 - 41 = 41
41	41

=> НОД(10127, 8323) = 41

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

	import java.util.Scanner;
	public class Solution {
	public static int getGreatestCommonDivisor(int a, int b) {
	if (a == b) {
	return a;
	}
	while (a != b) {
	if (a > b) {
	a = a - b;
	}
	else {
	b = b - a;
	}
	}
	int greatestCommonDivisor = a;
	return greatestCommonDivisor;
	}
	public static void main(String[] args) {
	Scanner read = new Scanner(System.in);
	int a = read.nextInt();
	int b = read.nextInt();
	int greatestCommonDivisor = getGreatestCommonDivisor(a, b);
	System.out.println(greatestCommonDivisor);
	// Close scanner
	read.close();
	}
	}

view raw ALGORITHMO-1-Euclidean-Algorithm-Implementation.java hosted with ❤ by GitHub