сряда, 22 декември 2010 г.

НОК - най-малко общо кратно

НОК - най-малко общо кратно

Число, което е кратно на няколко дадени числа, се нарича тяхно общо кратно. Най-малкото от общите кратни на две или повече числа се нарича най-малко общо кратно на тези числа. Алгоритъмът за най-малко общо кратно използва алгоритъм на Евклид за намиране на най-голям общ делител. Така НОК на две естествени числа N, M с НОД P се получава като отношение между произведенията на двете числа M*N и техния най-голям общ делител P. НОК = M * N / P
Пример: НОК на 14 (2*7) и 21 (3*7) е = 42 (2*3*7)
Пример: 36, 48
Изход: НОК = 144, т.к 36=12*3, 48=12*4, 144=12*3*4
Ако трябва да се обобщи алгоритъма за най-малко общо кратно за повече от две числа A1,A2,A3...An, то формулата би изглеждала НОК = НОД*(A1/НОД)*(А2/НОД) *...* (An/НОД)
Най-малкото общо кратно на две взаимно прости числа е тяхното произведение. Пример: 3 и 5, то най-малко общо кратно НОК = 15
Следва примерна програма, съдържаща решение на задача за намиране на най-малко общ кратно на две естествени числа:
view source
print?                 

Няма коментари:

Публикуване на коментар