Най-малко общо кратно на множество от N броя цели числа е най-малкото естествено число, което може да бъде разделено без остатък на всяко число, елемент на множеството. Пример: 12, 18 имат НОК 36.
В теорията на числата съществуват няколко алгоритъма за изчисляване на най-малко общо кратно (Least Common Multiple). Всеки от представените алгоритми се базира на тази основна теорема: произволно естествено число >1 може да бъде представено като произведение от прости числа.
Входни данни: множество с N>1 броя елементи естествени числа. Търси се най-малко общо кратно НОК за всички елементи на множеството.
А) Интуитивен алгоритъм / алгоритъм на таблицата се представя със следните стъпки:
началната стойност за търсен делител K се приравнява на K = 1;
построява се правоъгълна таблица с брой колони броя на разглежданите числа + 1 - колоната за открит делител;
последователно всяко от разглежданите числа се поставя в поредната колона;
стойността за търсен делител се увеличава с 1 - най-малкото просто число е 2;
докато някое от началните числа е кратно на търсения делител:
проверяват се записаните числа от всяка колона: ако числото не е кратно на търсения делител на следващия ред в таблицата се записва същото число, в противен случай на следващия ред от таблицата се записва неговото частно;
ако е било открито дори и едно кратно число в последната колона се записва стойността на търсения делител и процесът продължава от първата колона със същия делител;
ако не е било извършено нито едно деление стойността за търсения делител се увеличава с 1;
процесът продължава докато всички леви колони съдържат стойности >1.
НОК се изчислява като произведение на всички открити делители.
Пример:
35; 7; 24; 42; начална стойност за 4 елемента;
35; 7; 12; 21; : 2 - първият възможен делител е 2, в края на вложения цикъл НОК = 2; все още има елементи кратни на 2;
35; 7; 6; 21; : 2 - вторият възможен делител е 2, в края на вложения цикъл НОК = 2*2=4; все още има елементи кратни на 2;
35; 7; 3; 21; : 2 - третият възможен делител е 2, в края на вложения цикъл НОК = 4*2=8; вече няма елементи кратни на 2;
35; 7; 1; 7; : 3 - четвъртият възможен делител е 3, в края на вложения цикъл НОК = 8*3=24;
7; 7; 1; 7; : 5 - петият възможен делител е 5, в края на вложения цикъл НОК = 24*5=120;
1; 1; 1; 1; : 7 - шестият възможен делител е 7, в края на вложения цикъл НОК = 120*7=840;
Втори пример:
4, 7, 24, 21; начална стойност за избрани 4 елемента;
2; 7; 12; 21; : 2 - възможен делител е 2, в края на вложения цикъл НОК = 1*2; все още има елементи кратни на 2;
1; 7; 6; 21; : 2 - възможен делител е 2, в края на вложения цикъл НОК = 2*2; все още има елементи кратни на 2;
1; 7; 3; 21; : 2 - възможен делител е 2, в края на вложения цикъл НОК = 4*2; все още има елементи кратни на 2;
1; 7; 1; 7; : 3 - възможен делител е 3, в края на вложения цикъл НОК = 8*3
1; 1; 1; 1; : 7 - възможен делител е 7, в края на вложения цикъл НОК = 24*7
НОК =168
Б) разлагане на прости делители:
За търсене на прост делител (просто число явяващо се делител на разглежданото естествено число) се прилага алгоритъм памет за време - загуба на памет с цел увеличаване на бързодействието. Предварително се записват всички прости числа в желания интервал (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101...) и в цикъл се проверява дали някое от тях е делител.
35; 7; 24; 42; начална стойност за избрани 4 елемента;
35=5*7 има два различни прости делителя 5 и 7;
7 е просто число и има прост делител 7;
24=2*2*2*3 има има два различни прости делителя 2 и 3;
42=2*3*7 има три различни прости делителя 2, 3 и 7;
Ако в число простият делител се повтаря няколко пъти, то при изчисляване на НОК се взема най-големия брой повторения на този делител.
В начално множество числа са открити следните прости делители по брой и вид : 2, 2 ,2, 3, 5, 7. НОК е произведение от откритите делители НОК = 2*2*2*3*5*7 = 840
4, 7, 24, 21; начална стойност за избрани 4 елемента;
4 = 2*2 има два еднакви прости делителя 2;
7 е просто число и има прост делител 7;
24=2*2*2*3 има прости делители 2, 2, 2, 3;
21=3*7 има два различни прости делителя 3 и 7;
НОК е произведение от откритите делители НОК =2*2*2*3*7 = 168
В) вариант за изчисляване на най-малко общо кратно с предварително изчисляване на НОД - най-голям общ делител:
Формулата за изчисляване на най-малко общо кратно НОК може да бъде представена като:
НОК= А*В/НОД, както и варианта за проверка: изчисляване на стойностите m = A/НОД, n=B/НОД. Краен резултат за НОК = НОД*m*n.
Вариантът е удачен, ако броят на разглежданите числа е 2 - съществува ефективен алгоритъм за НОД - алгоритъм на Евклид.
Г) Алчен алгоритъм - използва елементи от алгоритъм на Евклид за изчисляване на най-голям общ делител НОД като ползва по-бързия вариант на алгоритъма с деление. Стъпките са:
35; 7; 24; 42; начална стойност за избрани 4 елемента;
5; 1; 24; 6; стойност на първия избран най-малък делител е 7; NOK = 7
1; 1; 24; 6; стойност на втория избран най-малък делител е 5; NOK = 7*5
1; 1; 4; 1; стойност на третия избран най-малък делител е 6; NOK = 35*6
1; 1; 1; 1; стойност на четвъртия избран най-малък делител е 4; NOK = 220*4=840
В следващия пример се илюстрира основния недостатък на алчния алгоритъм - търси най-малкия възможен делител без проверка за друго оптимално решение:
4; 7; 24; 21; : 4 NOK = 1*4
1; 7; 6; 21; : 6 НОК = 4*6 от избора на този делител започва грешката, в случая най-малкия прост делител е 3;
1; 7; 1; 21; : 7 NOK = 24*7
1; 1; 1; 3; : 3 NOK = 168*3
1; 1; 1; 1; NOK = 504
35; 7; 6; 21; начална стойност за избрани 4 елемента;
35; 7; 6; 21; НОК = 6 в случая е пропусната възможността за делител 3
35; 7; 1; 21; NOK = 6*7
5; 1; 1; 3; NOK = 42*3
5; 1; 1; 1; NOK = 126*5
1; 1; 1; 1; NOK = 630
Полученият резултат 630 е общо кратно за числата 35; 7; 6; 21, но това не е НОК.
Повод за разглеждане на този алгоритъм е неговата "невинна" грешка.
Реализирания проект работи със следните алгоритми за изчисляване на най-малко общо кратно: табличен, прости делители, алчен.
Изчисляване на най-малко общо кратно е свързано основно със задачи за изчисляване сума/разлика на дроби, задачи от работа, задачи от движение.
Разгледайте други реализирани примерни проекти, за които е ползвана подобна логическа структура на графичните обекти и/или приложени сходни алгоритми: прости числа, прости и съставни числа, алгоритъм на Евклид, брой и вид прости делители.