II Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
НАХОЖДЕНИЕ И ПРИМЕНЕНИЕ НОД И НОК
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение.
В каждодневной жизни человеку приходится решать большое число разного рода задач, которые требуют применения определённых алгоритмов. Когда мы приготавливаем чай, пользуемся определённым алгоритмом (иногда заданным инструкцией, напечатанной на упаковке).
Слово алгоритм стало широко употребляться в последнее время. Оно означает описание совокупности действий, составляющих некоторый процесс. Обычно здесь подразумевают процесс решения некоторой задачи, но и кулинарный рецепт, и инструкция по пользованию стиральной машиной, и ещё многие другие правила, не имеющие отношения к математике, являются алгоритмами
Данная работа знакомит с алгоритмами вычисления НОД и НОК. Знакомство с ними не только дополняет и углубляет математические знания, но и развивает интерес к предмету, любознательность и логическое мышление. Предлагаемая работа рассчитана на учеников, желающих повысить уровень математической подготовки, увидеть красоту математических выкладок и эстетику алгоритма Евклида.
Гипотеза:Есть алгоритмы нахождения НОД и НОК, которые являются удобными и не требующие громоздкого способа вычисления.
Цель исследования: изучить разные алгоритмы вычисления НОД и НОК, выявить наиболее рациональные способы решения, красиво и сравнительно просто приводящие к ответу.
Достижение поставленной цели требует решения следующих основных задач:
-
Рассмотреть несколько алгоритмов вычисления НОД и НОК
-
Сравнить алгоритмы для вычисления НОД и НОК
-
Провести анкетирование «Знание и использование НОД и НОК»
-
Составить список памятку «Применение НОД И НОК»
Предмет исследования: Алгоритмы вычисления НОД и НОК
Объект исследования: умения и навыки вычисления НОД и НОК
Методы исследования: Изучение специальной литературы по данному вопросу: энциклопедии, справочники и учебные пособия. Анкетирование. Сравнение и анализ. Обработка полученных данных (составление обобщающих таблиц, диаграмм). Для решения поставленных задач я изучал как литературные источники, так и интернет-источники, в том числе учебник под редакцией Н. Я. Виленкина «Математика. 6 класс».
Глава 1. Алгоритмы вычисления НОД и НОК 1.1. «Прадедушка» всех алгоритмовАлгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал».
В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.
Первое описание алгоритма находится в «Началах Евклида» (около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Позже алгоритм Евклида также был обобщен на другие математические структуры, такие как узлы и многомерные полиномы (многочлен от нескольких переменных) [2.2].
Для данного алгоритма существует множество теоретических и практических применений. В частности он широко распространён в электронной коммерции. Также алгоритм используется при решении диофантовых уравнений (Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами). Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми, в честь древнегреческого математика Диофанта Александрийского, например: Решить в целых числах уравнение x2 – xy – 2y2 = 7), при построении непрерывных дробей. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел. [2.3]
Долгое время алгоритм Евклида был самым эффективным способом отыскания наибольшего общего делителя, однако с появлением электронно-вычислительных машин ситуация изменилась Учет специфических особенностей выполнения арифметических операций компьютером позволил построить более эффективную (для программной реализации) версию алгоритма Евклида.
1. 2. Алгоритмы вычисления НОД 1.2.1 Алгоритм простого перебораЧтобы найти наибольший общий делитель двух данных натуральных чисел можно действовать по определению: выписать все делители этих чисел, выделить среди них общие и выбрать среди всех общих делителей наибольший.
Пример. Найдем все делители чисел 54 и 36.
54 делится на 1; 2; 3; 6; 9; 18; 27; 54.
36 делится на 1; 2; 3; 4; 6; 9; 18; 36.
Общими делителями являются числа: 1, 2, 3, 6, 9, 18.
Значит НОД(54; 36)=18
1.2.2 Нахождение НОД с помощью разложения чисел на простые множителиРассмотрим еще один способ нахождения НОД. Наибольший общий делитель может быть найден по разложениям чисел на простые множители.
Что такое разложение на множители? Это способ превращения неудобного и сложного примера в простой и симпатичный. Встречается на каждом шагу и в элементарной математике, и в высшей. Подобные превращения на математическом языке называются тождественными преобразованиями выражений. Смысл любого тождественного преобразования - это запись выражения в другом виде с сохранением его сути.
Смысл разложения на множители предельно прост и понятен. Прямо из самого названия. Например, надо разложить число 12. Можно смело записать: 12=3·4
А можно разложить 12 по-другому: 12=3·4=2·6=3·2·2=0,5·24=........
Вариантов разложения - бесконечное количество.
Сформулируем правило: НОД двух целых положительных чисел a и b равен произведению всех общих простых множителей, находящихся в разложениях чисел a и b на простые множители.
Приведем пример для пояснения правила нахождения НОД.
Пусть нам известны разложения чисел 220 и 600 на простые множители, они имеют вид 220=2·2·5·11 и 600=2·2·2·3·5·5. Общими простыми множителями, участвующими в разложении чисел 220 и 600, являются 2, 2 и 5. Следовательно, НОД(220, 600)=2·2·5=20.
Таким образом, если разложить числа a и b на простые множители и найти произведение всех их общих множителей, то будет найден наибольший общий делитель чисел a и b.
Пример. Найдите наибольший общий делитель чисел 72 и 96.
Решение. Разложим числа 72 и 96 на простые множители.
72=2·2·2·3·3 и 96=2·2·2·2·2·3. Общими простыми множителями являются 2, 2, 2 и 3. Таким образом, НОД(72, 96)=2·2·2·3=24.
Ответ: НОД(72, 96)=24.
В заключение этого пункта заметим, что справедливость приведенного правила нахождения НОД следует из свойства наибольшего общего делителя, которое утверждает, что
НОД(m·a, m·b)=m·НОД(a, b), где m – любое целое положительное число.
1.2.3. Алгоритм ЕвклидаОдним из простейших алгоритмов нахождения наибольшего общего делителя является Алгоритм Евклида. Он может быть реализован, как при помощи вычитания, так и деления. Рассмотрим каждый из этих двух способов.
а) Описание алгоритма нахождения НОД вычитанием:
Из большего числа вычитаем меньшее. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла). Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
Переходим к пункту 1.
Пример:
Найти НОД для 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6
б) Описание алгоритма нахождения НОД делением:
Большее число делим на меньшее. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла). Если есть остаток, то большее число заменяем на остаток от деления. Переходим к пункту 1.
Пример.
Пусть требуется найти НОД(102;84). Разделим одно число на другое и определим остаток.
102=84*1+18 0