This content originally appeared on DEV Community and was authored by
(Първо публикувано на 11.01.2017)
Днешният алгоритъм не е нищо специално, а просто още един начин по който можем да намерим най-голям общ делител (НОД) на 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):
Намиране на НОК:
—
Това е за днес! Ако видите някоя грешка — сигнализирайте ми! 😉
This content originally appeared on DEV Community and was authored by
| Sciencx (2025-07-20T14:10:22+00:00) AlgorithmO #10 — Двоичен алгоритъм за НОД (+ намиране на НОК). Retrieved from https://www.scien.cx/2025/07/20/algorithmo-10-%d0%b4%d0%b2%d0%be%d0%b8%d1%87%d0%b5%d0%bd-%d0%b0%d0%bb%d0%b3%d0%be%d1%80%d0%b8%d1%82%d1%8a%d0%bc-%d0%b7%d0%b0-%d0%bd%d0%be%d0%b4-%d0%bd%d0%b0%d0%bc%d0%b8/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.