Това, което научих, е, че започването на каквото и да е, е най-трудната част. Затова трябва да направим първата стъпка максимално лесна и след това става по-лесно да продължим напред, тъй като сме си изградили "инерция".
И все пак отново се връщам на този алгоритъм. Причината е, че има още една вариация, която не съм разглеждал. Не се плашете, тя е също толкова лесна за схващане и понякога дори по-практична.
Нека да видим...
---
 |
| Евклид (освен всичко друг) е бил и фен на епичните бради... :) |
ОПИСАНИЕ:
Този алгоритъм е ефективен при малки числа. За по-големи числа се ползват други по-сложни, но и по-бързи алгоритми като например двоичен алгоритъм за намиране на НОД (предстои да бъде разгледан и тук 😅).
АЛГОРИТЪМ:
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).
ПРИМЕР:
Нека използваме един от примерите от другия ми пост за Евклид.
Виждаме бързо, че 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):
---
Това е за днес! Ако видите някоя неточност (несъмнено ще се появи такава рано или късно)... е, вече знаете, но... кажете ми! 😁
Няма коментари:
Публикуване на коментар