Разработка алгоритма вычисления наименьшего общего кратного системы чисел

     90 = 2 • 3 • 3 • 5,

     60 = 2 • 2 • 3 • 5,

     50 = 2 • 5 • 5.

     Наименьшее  общее кратное должно делиться на 90, значит, в состав его должны входить  все множители числа 90. Далее, наименьшее кратное должно делиться и на 60, т. е. в его состав должны входить множители и этого числа, наконец, одновременно с этим оно должно делиться и на последнее число —50, следовательно, оно должно содержать множители и этого последнего числа. Учитывая все эти обстоятельства, поступим так: выпишем сначала все множители первого числа (90), а затем, чтобы обеспечить делимость искомого кратного на остальные числа, добавим к написанным множителям из других чисел те множители, которых недостаёт в разложении числа 90. Получим следующее:

     НОК (90, 60, 50) = 2 • 3 • 3 • 5• 2• 5 = 900.

     Отсюда  получаем правило:

     Чтобы   найти   наименьшее  общее кратное нескольких  чисел надо разложить эти числа на простые множители,   затем взяв разложение одного из них, приписать к нему недостающие простые множители из разложений других чисел и перемножить их между собой.

     Если  большее из данных чисел делится  на все остальные, то оно и будет  наименьшим кратным для этих чисел. Например, наименьшим общим кратным  чисел 120, 60 и 40 будет 120. Если никакая пара данных чисел не имеет общих множителей, то для нахождения наименьшего общего кратного данных чисел их нужно перемножить.

      С помощью алгоритма Евклида (есть числа a,b и последовательность R1>R2>R3>…>RN, где каждое RK - это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело. Тогда НОД(a,b), наибольший общий делитель a и b, равен RN, последнему ненулевому члену этой последовательности) можно найти НОД для первых двух чисел, «цепляя» следующее число для нахождения следующего НОД, и так до тех пор, пока совокупность чисел не закончится.

         Для нахождения НОК первых двух чисел используем следующий алгоритм:  

     1)  представить каждое число как произведение его простых множителей, например:

     504 = 2 · 2 · 2 · 3 · 3 · 7 ,

     2)  записать степени всех простых множителей:

     504 = 2 · 2 · 2 · 3 · 3 · 7 = 23 · 32 · 71,

     3)  выписать все простые делители (множители) каждого из этих чисел;       

     4)  выбрать наибольшую степень каждого из них, встретившуюся во всех разложениях этих чисел;

     5)  перемножить эти степени. 
 
 
 
 
 
 
 
 
 
 
 
 
 

     2.3. Разработка блок – схемы алгоритма  вычисления наименьшего общего кратного

       
 
 
 

       
 

       
 
 
 

 
 

 

 

 
 
 
 
 
 
 

     Глава 3. ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО АЛГОРИТМА  ВЫЧИСЛЕНИЯ НАИМЕНЬШЕГО ОБЩЕГО КРАТНОГО 

     3.1. Задачи и условия исследования  алгоритма 

     Для достижения поставленной перед нами цели, необходимо поставить перед собой задачи и условия исследования алгоритма. Для реализации алгоритма вычисления наименьшего общего кратного целых чисел был выбран метод блок-схем как достаточное условие исследования алгоритма. 

3.2 Программная реализация алгоритма 

program naimenshee_obshee_kratnoe;

var n,m:integer;

    i,k:integer;

    delitsya:boolean;

begin

     write('Vvedite N: ');

     readln(n);

     write('Vvedite M: ');

     readln(m);

    if (m<>0) and (n<>0) then

     begin

        k:=n*m;

        i:=k;

       while i>0 do

        begin

         if (i mod n=0) and (i mod m=0) then

             k:=i;

          i:=i-1;

        end;

        writeln('NOK ',m,' i ',n,' raven ',k)

     end

     else writeln('Na nol delit nelzya');

     readln;

end. 

3.3 Результаты исследования алгоритма 

     Результатом исследования алгоритма вычисления наименьшего общего кратного чисел является его программная реализация в среде программирования Pascal.  В алгоритме использовался цикл while с вложенным ветвлением, оператор if для проверки корректности данных (чисел), вводимых пользователем. Цикл продолжается пока переменная i не будет больше нуля, это достигается постоянным понижение ее на одну единицу.  

Заключение 

     В ходе исследования алгоритма были получены практические результаты, которые подтвердили  адекватность разработанного алгоритма, при проверки его на конкретном примере.

     Алгоритм  вычисления наименьшего кратного чисел довольно быстро вычисляет необходимый результат, оперируя даже с относительно большими числами. Это обусловлено простотой алгоритма и вполне понятной программной реализацией. Код программы не загроможден сложными вычислительными операциями, что позволяет алгоритмам достаточно быстро выдавать вычисленный результат.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Библиографический список 

     

1. Алгебра и  теория чисел. Под ред. Н. Я. Виленкина. Москва: Просвещение, 1984.
2. Архангельский А. Я. Программирование в Delphi 6. Москва: ЗАО Бином, 2003.
3. Архангельский А. Я. Delphi 7. Справочное пособие. Москва: ООО Бином-Пресс, 2004.
4. Курош А. Г. Курс высшей алгебры. Москва: Наука, 1971.
5. Ляпин Е. С., Евсеев А. Е. Алгебра и теория чисел. Часть II. Линейная алгебра и полиномы. Москва: Просвещение, 1978.
6. Мантуров О. В.  и др. Математика в понятиях, определениях и терминах. Часть 2. Москва: Просвещение, 1982.
7. Попов В.Б. Turbo Pascal. Москва: Финансы и статистика, 2000.
8. Потапов М. К., Александров В. В., Пасиченко П. И. Алгебра и анализ элементарных функций. Москва: Наука, 1980.
9. Сабинина Л. В. Математика в понятиях, определениях и терминах. Часть I. Москва: Просвещение, 1978.
10. Сборник задач по алгебре. Под ред. А. И. Кострикина. Москва: Наука, 1987.
11. Смолин Ю. Н. Алгебра и теория чисел. Перемь:1996.
12. Солодовников А. С., Родина М. А. Задачник-практикум по алгебре. Часть IV. Москва: Просвещение, 1985.
13. Фадеев Д. К. Лекции по алгебре. Москва: Наука, 1984.
14. Фадеев Д. К., Соминский И. С. Сборник задач по высшей алгебре. Москва: Наука, 1968.
15. Шварцбурд С. И. Избранные вопросы математики. Москва: Просвещение, 1980.