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

Започнах тази поредица с един от най-простите съществуващи алгоритми - този на Евклид, за да мога лесно да премахна оправдания като "ама това е прекалено трудно и май не го разбирам достатъчно, за да се опитам да науча някой друг на него". 

Това, което научих, е, че започването на каквото и да е, е най-трудната част. Затова трябва да направим първата стъпка максимално лесна и след това става по-лесно да продължим напред, тъй като сме си изградили "инерция".

И все пак отново се връщам на този алгоритъм. Причината е, че има още една вариация, която не съм разглеждал. Не се плашете, тя е също толкова лесна за схващане и понякога дори по-практична.

Нека да видим...

---

Евклид (освен всичко друг) е бил и фен на епичните бради... :)

ОПИСАНИЕ:

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

Този алгоритъм е ефективен при малки числа. За по-големи числа се ползват други по-сложни, но и по-бързи алгоритми като например двоичен алгоритъм за намиране на НОД (предстои да бъде разгледан и тук 😅).

АЛГОРИТЪМ:

Нека имаме две естествени числа 'a' и 'b'.

1) Ако b == 0 ('b' има стойност 0), то 'a' е НОД на числата 'a' и 'b'.
2) Ако b != 0 ('b' има стойност различна от 0), то:
  - a_previous := a (присвояваме текущата стойност на 'a' във временна променлива)
  - a := b (присвояваме стойността 'b' на 'а'),
  - b := a_previous % b (присвояваме остатъкa от делението на 'a' (стойността преди присвояването) на 'b'... на 'b' 😀)
 - отиваме на стъпка 1).

ПРИМЕР:

Нека използваме един от примерите от другия ми пост за Евклид.

НОД(2505, 9775) = ?

Виждаме бързо, че a = 2505 и b = 9775.

За съжаление 'b' не е равно на 0, така че имаме работа за вършене.

Вече 'a' присвоява стойността на 'b', т.е. a := 9775. Но пък ни трябва и предишната стойност на 'a', тъй като ще я използваме при следващото деление. Да кажем, че a_previous := 2505.

Сега трябва да намерим новата стойност на 'b'. Тя ще бъде равна на a_previous % b (остатъка от делението на двете числа). С други думи, b = 2505 % 9775. Tъй като 9775 се съдържа 0 пъти в 2505, остава ни 2505, т.е. b := 2505.

След тази итерация, 'a' и 'b' изглеждат така:

a = 9775

b = 2505

Продължаваме по същия начин! 

Правим следните заключения:

- a = 9775, b = 2505

- b != 0 ('b' не е равно на 0)

- a_previous := 9775

- a := b => a = 2505 (запазваме предишната стойност на 'a' и присвояваме на 'a' нова стойност, която е равна на 'b')

- b := a_previous % b = 9775 % 2505 = 2260 (защото след целочислено деление, 9775 / 2505 = 3 и имаме остатък 2260) => b = 2260

След тази итерация, 'a' и 'b' изглеждат така:

a = 2505

b = 2260

Общо взето това беше цялата "сложнотийка" на алгоритъма.

Продължаваме така докато 'b' не стане 0.

... ще ви спестя коментарите си по всяка итерация (този път 😅 ).

Правим следните заключения:

- а = 2505, b = 2260

- b != 0 

- a_previous := 2505

- a := b => a = 2260 

- b := a_previous % b = 2505 % 2260 = 245 (2505 / 2260 = 1 и остатък 245) => b = 245

След тази итерация, 'a' и 'b' изглеждат така:

a = 2260

b = 245

Правим следните заключения:

- а = 2260, b = 245

- b != 0 

- a_previous := 2260

- a := b => a = 245

- b := a_previous % b = 2260 % 245 = 55 (2260 / 245 = 9 и остатък 55) => b = 55

След тази итерация, 'a' и 'b' изглеждат така:

a = 245

b = 55

Правим следните заключения:

- а = 245, b = 55

- b != 0 

- a_previous := 245

- a := b => a = 55

- b := a_previous % b = 245 % 55 = 25 (245 / 55 = 4 и остатък 25) => b = 25

След тази итерация, 'a' и 'b' изглеждат така:

a = 55

b = 25

Правим следните заключения:

- а = 55, b = 25

- b != 0 

- a_previous := 55

- a := b => a = 25

- b := a_previous % b = 55 % 25 = 5 (55 / 25 = 2 и остатък 5) => b = 5

След тази итерация, 'a' и 'b' изглеждат така:

a = 25

b = 5

Правим следните заключения:

- а = 25, b = 5

- b != 0 

- a_previous := 25

- a := b => a = 5

- b := a_previous % b = 25 % 5 = 0 (25 / 5 = 5 и остатък 0) => b = 0

След тази итерация, 'a' и 'b' изглеждат така:

a = 5

b = 0

И така... стигнахме до финала! Вече b = 0, следователно НОД(2505, 9775) = a = 5.

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

	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;
	}
	public static void main(String[] args) {
	System.out.println(
	getGreatestCommonDivisor(2505, 9775)
	);
	}
	}

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

---

Това е за днес! Ако видите някоя неточност (несъмнено ще се появи такава рано или късно)... е, вече знаете, но... кажете ми! 😁