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

(Първо публикувано на 02.12.2016)

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

В момента изучавам алгоритми и отново се сблъсквам с гореописания проблем. Затова ще се опитам с тази поредица от 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) = ?

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

—

НОД(10127, 8323) = ?

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