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

АСТРАХАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Филиал  в городе Знаменске

Факультет информатика 
 

Кафедра математики и информатики 
 
 
 
 

КУРСОВАЯ  РАБОТА

по дисциплине «ЭЛЕМЕНТЫ АБСТРАКТНОЙ И КОМПЬЮТЕРНОЙ АЛГЕБРЫ»

РАЗРАБОТКА АЛГОРИТМА ВЫЧИСЛЕНИЯ НАИМЕНЬШЕГО ОБЩЕГО КРАТНОГО СИСТЕМЫ ЧИСЕЛ 

      Выполнил:

      студент группы ИН41(0)

      очного отделения 

      Ивашиненко В.А. 

      Научный руководитель:

      доктор технических  наук

      профессор В.И. Лобейко 
 

     

 
ОГЛАВЛЕНИЕ

     

Введение……………………………………………………………………...........3

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

     1.1. Существующее состояние темы исследования……………………...4

     1.2. Постановка задачи разработки алгоритма вычисления наименьшего общего кратного…………………………………………………………………..5

Глава 2. РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ  ПОСТАВЛЕННОЙ ЗАДАЧИ…………………………………………………………………………...6

      2.1. Вывод основных математических  соотношений вычисления наименьшего общего кратного целых чисел……………………………………6 2.2. Разработка вычисления наименьшего общего кратного…….10 2.3. Разработка блок – схемы алгоритма вычисления наименьшего общего кратного……………………..…………………………………………..12

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

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

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

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

Заключение……………………………………………………………………….15

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

Введение 

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

     Если мы переходим улицу на регулируемом светофором перекрёстке, мы выполняем определённый алгоритм, когда же переходим улицу в месте, не регулируемом светофором, выполняем другой алгоритм (эти алгоритмы заданы правилами уличного движения). И когда мы берём книги в библиотеке, мы выполняем определённые правила пользования библиотечными книгами, т.е. тоже определенный алгоритм.

     Можно ли перечислить все задачи, при решении которых мы используем определённые алгоритмы?

     Однако  слово алгоритм стало широко употребляться примерно в 1985 году. Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

     При работе с большими составными числами их разложение на простые множители, как правило, неизвестно. Но для многих прикладных задач теории чисел поиск разложения числа на множители является важной, часто встречающейся практической задачей. В теории чисел существует сравнительно быстрый способ вычисления НОД и НОК двух чисел. .

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

     Объект  исследования – нахождение наименьшего общего кратного чисел.

     Предмет исследования – разработка алгоритма для нахождения наименьшего общего кратного чисел. 
 

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

     1.1. Существующее состояние темы исследования 

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

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

     Для разработки алгоритма вычисления наибольшего  общего делителя необходимо выполнить  следующие задачи:

     1) анализ существующей литературы  по данной теме;

     2) вывод основных математических  соотношений для вычисления наименьшего общего кратного;

     4) выбор программного обеспечения для реализации алгоритма вычисления наименьшего общего кратного чисел. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Глава 2. РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ  ПОСТАВЛЕННОЙ ЗАДАЧИ

     2.1. Вывод основных математических соотношений вычисления наименьшего общего кратного целых чисел 

       Целыми называются числа ..., -3, -2, -1, 0, 1, 2, 3,..., т.е. натуральные числа 1, 2, 3, 4,..., а также нуль и отрицательные числа -1, -2, -3, -4,... . Множество всех целых чисел обозначается через Z (от немецкого слова Zahl - число).

     Сумма, разность и произведение двух целых  чисел - также целые числа. Если для  трех целых чисел a, b и с выполнено равенство a = bc, то говорят: а делится на b или b делит а и применяют соответственно обозначения a:b, b/a. При этом а называют кратным числа b, а b - делителем числа а.

     Свойства  делимости целых  чисел:

     1) а делится на а (рефлексивность);

     2) если а делится на b, b делится на а, то a= b+ или -b;

     3) если а делится на b, b делится на с, то а делится на с (транзитивность);

     4). если a+b+c=0, а а делится на d, b делится на d, то и с делится на d;

5) если ad делится на bd, и d≠0 то, а делится на b. 

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

 Для него применяют обозначения: 

     НОК(a1,…….,an) = [a1,……..,an] 

     Теорема. Наименьшее общее кратное двух целых чисел а и b равно произведению этих чисел, деленному на их наибольший общий делитель, т.е.

     

     Доказательство: Пусть N:a, N:b, т.е. . Пусть также . Тогда . По условию делится на .

     Отсюда  делится на . По теореме Евклида делится на , т.е. . Мы получили, что произвольное общее кратное можно записать в виде: Наименьшее положительное целое число такого вида при  t=1 имеет вид . А это и требовалось доказать.

       Следствие. Произвольное общее кратное чисел а и b есть кратное их наименьшего общего кратного.

     Теорема. Любое натуральное  число, отличное от 1, можно представить в виде произведения простых чисел и притом единственным образом с точностью до порядка следования сомножителей.

     Доказательство  теоремы существования проведем методом полной математической индукции по числу n.

     Простое число мы рассматриваем как произведение простых чисел, состоящее из одного множителя. Поэтому для простых чисел утверждение теоремы существования верно и, в частности, для числа 2.  Предположим, что утверждение теоремы верно при всех k, для которых .

     Обозначим через p наименьший целый положительный отличный от 1 делитель числа n.  Ясно, что p - простое число и ,1.Если n=p, то утверждение теоремы верно. Если , то к n можно применить предположение индукции, так как . Тогда n, а, следовательно, и можно представить в виде произведения простых чисел. Теорема существования доказана.

     Доказательство  теоремы единственности проведем методом от противного. Пусть для некоторого натурального числа п имеется два представления в виде произведения простых чисел и пусть . Предположим, что Тогда и произведение делится на . По теореме Евклида отсюда следует, что делится на . Повторяя рассуждения при предположении получим, что должно равняться одному из чисел . Изменив нумерацию, можно добиться того, что . Итак, мы имеем равенство

     

     Отсюда, получаем:

     

     Вновь повторяя рассуждения, получим  Равенство невозможно, т.е. l+k>1. Предположение l<k приводит к такому же противоречию. Остается лишь одна возможность k=l. Итак, представления оказались тождественны. Теорема доказана.

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

     

     Из  основной теоремы арифметики следует, что все делители числа n можно записать в виде:

     

     Из  этой теоремы также вытекает и  второй способ нахождения НОД и НОК. Предположим, что числа а и b представлены в виде:

     

     

     Здесь к каноническому представлению  числа а приписаны в нулевой степени, т.е простые числа, которые входят в каноническое представление числа b, но не входят в представление числа а. Соответственно проделано тоже с каноническим представлением числа b.

     Тогда:

     Свойства  наибольшего общего делителя и наименьшего общего кратного нескольких натуральных чисел.

     Свойство 1. HOD(a,b,c)=HOD(HOD(a,b), c)

     Свойство 2. HOK(a,b,c)=HOK(HOK(a,b),c)

     Свойство 3. HOD(ac,bc)=cHOD(a,b)

     Свойство 4. HOK(ac,bc)=cHOK(a,b)

     Свойство 5. HOD(n,n+1,n+2)=1

     Свойство 6. Числа aHOD(a,b) и bHOD(a,b) взаимно простые.

     Свойство 7. HOD(n,n+k)=HOD(n,k)=1

     Свойство 8. HOK(a,b)=abHOD(a,b). 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

     Пусть требуется найти наименьшее общее  кратное чисел 90, 60 и 50. Разложим предварительно эти числа на простые множители: