(Първо публикувано на 11.01.2017)
Започнах тази поредица с един от най-простите съществуващи алгоритми — този на Евклид, за да мога лесно да премахна оправдания като “ама това е прекалено трудно и май не го разбирам достатъчно, за да се опитам да науча някой друг на него”.
Това, което научих, е, че започването на каквото и да е, е най-трудната част. Затова трябва да направим първата стъпка максимално лесна и след това става по-лесно да продължим напред, тъй като сме си изградили “инерция”.
И все пак отново се връщам на този алгоритъм. Причината е, че има още една вариация, която не съм разглеждал. Не се плашете, тя е също толкова лесна за схващане и понякога дори по-практична.
Нека да видим…
Евклид (освен всичко друг) е бил и фен на епичните бради… :)
ОПИСАНИЕ:
Алгоритъмът на Евклид се използва за намиране на най-голям общ делител (НОД) на 2 числа. НОД представлява най-голямото число, на което и 2-те числа се делят без остатък.
Този алгоритъм е ефективен при малки числа. За по-големи числа се ползват други по-сложни, но и по-бързи алгоритми като например двоичен алгоритъм за намиране на НОД (предстои да бъде разгледан и тук 😅).
АЛГОРИТЪМ:
Нека имаме две естествени числа ‘a’ и ‘b’.
Ако b == 0 (‘b’ има стойност 0), то ‘a’ е НОД на числата ‘a’ и ‘b’.
Ако 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):
—
Това е за днес! Ако видите някоя неточност (несъмнено ще се появи такава рано или късно)… е, вече знаете, но… кажете ми! 😁
Top comments (0)