AlgorithmO #10 - Двоичен алгоритъм за НОД (+ намиране на НОК)

Днешният алгоритъм не е нищо специално, а просто още един начин по който можем да намерим най-голям общ делител (НОД) на 2 числа. Предимството му пред алгоритъма на Евклид е, че обикновено се представя по-добре при реални тестове. Имплементацията му е малко по-объркваща, но не е нищо особено като цяло.

За да не бъде изключително скучен този пост, ще ви спомена как да намерим и НОК (най-малко общо кратно - т.е., най-малкото число, което се дели на няколко други числа и е тяхно "кратно"). 😉

---

Кой не обича math jokes... :)

ОПИСАНИЕ:

Двоичният алгоритъм за намиране на НОД (понякога наричан Stein's algorithm - алгоритъм на Стайн, Стейн, Щайн... кой знае?) използва набор от правила, с които намалява изчисленията по намирането на НОД.

Ще отбележим 2-те числа, на които търсим НОД, с 'u' и 'v'.

Алгоритъмът изисква време пропорционално на квадрата на общия брой на битове, които 'u' и 'v' заемат. Въпреки че поне едно от числата се редуцира на всяка стъпка, изваждането и преместването не се извършват за константно време всеки път (особено за много големи числа) , но все пак на практика те са доста бързи операции.

(последният параграф взет от дадените ми лекции по Проектиране и анализ на алгоритми :))

АЛГОРИТЪМ:

НОД (u, v) = ?

1) НОД(0, v) = v
2) НОД(u, 0) = u

* НОД(0, 0) е неопределен.

3) u, v - четни
-> НОД(u,v) = 2 * НОД (u/2, v/2)

4) u - четно, v - нечетно

-> НОД(u,v) = НОД(u/2, v)

5) u - нечетно, v - четно
-> НОД(u,v) = НОД(u, v/2)

6) u, v - нечетни
- u >= v
-> НОД(u,v) = НОД( (u-v)/2, v )
- v > u
-> НОД(u,v) = НОД( u, (v-u)/2 )

Намиране на НОК (бонус алгоритъм):

Намирането на НОК става изключително лесно след като знаем НОД на 2-те числа. Прилагаме формулата:

НОК(a, b) = (a * b) / НОД(a, b)

За повече от 2 числа, прилагаме НОК(a, b, c) = НОК(а, НОК(b, c)).

ПРИМЕР:

Ето няколко примера, които илюстрират как точно се прилага двоичният алгоритъм на всяка стъпка.

Смятам, че няма нужда от обяснения този път. 😄

===

НОД(728, 140) =
= 2 * НОД(364, 70) =
= 2 * 2 * НОД(182, 35) =
= 2 * 2 * НОД(91, 35) =
= 2 * 2 * НОД( (91-35)/2, 35 ) =
= 2 * 2 * НОД(56/2, 35)
= 2 * 2 * НОД(28, 35) =
= 2 * 2 * НОД(28/2, 35) =
= 2 * 2 * НОД(14, 35) =
= 2 * 2 * НОД(14/2, 35) =
= 2 * 2 * НОД(7, 35) =
= 2 * 2 * НОД( 7, (35-7)/2 ) =
= 2 * 2 * НОД(7, 28/2) =
= 2 * 2 * НОД(7, 14) =
= 2 * 2 * НОД(7, 14/2) =
= 2 * 2 * НОД(7, 7) =
= 2 * 2 * НОД( (7-7)/2, 7) ) =
= 2 * 2 * НОД(0, 7) =
= 2 * 2 * 7 =
= 28

===

НОД(2505, 9775) =
= НОД( 2505, (9775-2505)/2 ) =
= НОД(2505, 7270/2)
= НОД(2505, 3635)
= НОД( 2505, (3635-2505)/2 ) =
= НОД(2505, 1130/2) =
= НОД(2505, 565)
= НОД( (2505-565)/2, 565) =
= НОД(1940/2, 565) =
= НОД(970, 565) =
= НОД(970/2, 565) =
= НОД(485, 565) =
= НОД( 485, (565-485)/2) ) =
= НОД(485, 80/2) =
= НОД(485, 40) =
= НОД(485, 40/2) =
= НОД(485, 20) =
= НОД(485, 20/2) =
= НОД(485, 10) =
= НОД(485, 10/2) =
= НОД(485, 5) =
= НОД( (485-5)/2, 5 ) =
= НОД(480/2, 5) =
= НОД(240, 5) =
= НОД(240/2, 5) =
= НОД(120, 5) =
= НОД(120/2, 5) =
= НОД(60, 5) =
= НОД(60/2, 5) =
= НОД(30, 5) =
= НОД(30/2, 5) =
= НОД(15, 5) =
= НОД( (15-5)/2, 5) =
= НОД(10/2, 5) =
= НОД(5, 5) =
= НОД( (5-5)/2, 5 ) =
= НОД(0, 5) =
= 5

===

НОД(10127, 8323) =
= НОД( (10127-8323)/2, 8323 ) =
= НОД(1804/2, 8323) =
= НОД(902, 8323) =
= НОД(902/2, 8323) =
= НОД(451, 8323) =
= НОД( 451, (8323-451)/2 ) =
= НОД(451, 7872/2) =
= НОД(451, 3936) =
= НОД(451, 3936/2) =
= НОД(451, 1968) =
= НОД(451, 1968/2) =
= НОД(451, 984) =
= НОД(451, 984/2) =
= НОД(451, 492) =
= НОД(451, 492/2) =
= НОД(451, 246) =
= НОД(451, 246/2) =
= НОД(451, 123) =
= НОД( (451-123)/2, 123 ) =
= НОД(328/2, 123) =
= НОД(164, 123) =
= НОД(164/2, 123) =
= НОД(82, 123) =
= НОД(82/2, 123) =
= НОД(41, 123) =
= НОД( 41, (123-41)/2 ) =
= НОД(41, 82/2) =
= НОД(41, 41) =
= НОД( (41-41)/2, 41 ) =
= НОД(0, 41) =
= 41

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


Намиране на НОК:



---

Това е за днес! Ако видите някоя грешка - сигнализирайте ми! 😉