XVI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке. Летняя площадка 2022
Альтернативные алгоритмы вычисления НОД и НОК. Алгоритм Евклида
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
С понятиями наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) учащиеся средней школы, встречаются в шестом классе. Данная тема всегда трудна для усвоения. Дети часто путают эти понятия, не понимают, зачем их нужно изучать. В последнее время и в научно-популярной литературе встречаются отдельные высказывания о том, что данный материал нужно исключить из школьной программы. Думаю, что это не совсем верно, и изучать его нужно если не на уроках, то во внеурочное время на занятиях школьного компонента обязательно, так как это способствует развитию логического мышления школьников, повышению скорости вычислительных операций, умению решать задачи красивыми методами.
Данная работа знакомит с алгоритмами вычисления НОД. Знакомство с ними не только дополняет и углубляет знания, но и развивает интерес к предмету, любознательность и логическое мышление. Предлагаемая работа рассчитана на учеников, желающих повысить уровень математической подготовки, увидеть красоту математических выкладок и эстетику алгоритма Евклида, а так же помочь учащимся не бояться громоздких и очень трудных с виду задач с НОД, помня пословицу: «Волков бояться, в лес не ходить!».
Гипотеза: Если алгоритм Евклида является удобным и быстрым способом вычисления НОД, то нужно знакомить с ним учащихся и чаще использовать.
Цель исследования: изучить разные алгоритмы вычисления НОД, выявить наиболее рациональные способы решения, красиво и сравнительно просто приводящие к ответу.
Достижение поставленной цели требует решения следующих основных задач:
Рассмотреть несколько алгоритмов вычисления НОД
Сравнить алгоритмы вычисления НОД
Провести анкетирование
Составить список рекомендаций
Предмет исследования: Алгоритмы вычисления НОД
Объект исследования: умения и навыки вычисления НОД
Методы исследования:
Изучение специальной литературы по данному вопросу: энциклопедии, справочники и учебные пособия.
Анкетирование.
Сравнение и анализ.
Обработка полученных данных (составление обобщающих таблиц, диаграмм)
Работа в компьютерных программах Microsoft Word, Excel, Microsoft PowerPoint
Глава 1. «Прадедушка» всех алгоритмов
Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал».
В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.
Первое описание алгоритма находится в «Началах Евклида» (около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Однако в 19 веке он был обобщён на другие типы чисел, такие как целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как «Евклидово кольцо». Позже алгоритм Евклида также был обобщен на другие математические структуры, такие как узлы и многомерные полиномы.
Долгое время алгоритм Евклида был самым эффективным способом отыскания наибольшего общего делителя, однако с появлением электронно-вычислительных машин ситуация изменилась (алгоритм Евклида, как нетрудно понять, появился задолго до вычислительных машин). Учет специфических особенностей выполнения арифметических операций компьютером позволил построить более эффективную (для программной реализации) версию алгоритма Евклида.
Глава 2. Алгоритмы вычисления НОД
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
2.2 Нахождение НОД с помощью разложения чисел на простые множители
Рассмотрим еще один способ нахождения НОД. Наибольший общий делитель может быть найден по разложениям чисел на простые множители.
Сформулируем правило: НОД двух целых положительных чисел 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 – любое целое положительное число.
2.3. Алгоритм Евклида
Одним из простейших алгоритмов нахождения наибольшего общего делителя является Алгоритм Евклида. Он может быть реализован, как при помощи вычитания, так и деления. Рассмотрим каждый из этих двух способов.
а) Описание алгоритма нахождения НОД вычитанием:
Из большего числа вычитаем меньшее.
Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
Переходим к пункту 1.
Пример:
Найти НОД для 42 и 18.
42 - 18 = 24
24 – 18 = 6
18 - 6 = 12
12 – 6 = 6
6-6=0
Конец: НОД – это уменьшаемое или вычитаемое. НОД (42, 18)=6
б) Описание алгоритма нахождения НОД делением:
Большее число делим на меньшее. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
Если есть остаток, то большее число заменяем на остаток от деления.
Переходим к пункту 1.
Пример.
Пусть требуется найти НОД(102;84). Разделим одно число на другое и определим остаток.
102=84*1+18 0 <18<84
Теперь проделаем такую же операцию для чисел 84 и 18:
84=18*4+ 12 0 <12<18
Следующий шаг - для 18 и 12:
18=12*1+6 0 <6<12
Теперь - для 12 и 6:
12=6*2+0 0-остаток. Процесс закончился.
2.4. Бинарный алгоритм Евклида.
Бинарный алгоритм вычисления наибольшего общего делителя, как понятно из названия, находит наибольший общий делитель двух целых чисел. В сравнении с хорошо известным алгоритмом Евклида, этот на практике работает быстрее, но в тоже время немного уступает первому в простоте реализации. Алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году, израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД:
НОД(2n, 2m) = 2 НОД(n, m)
НОД(2n, 2m+1) = НОД(n, 2m+1)
НОД(-n, m) = НОД(n, m)
2.5. Нахождение НОД трех и большего количества чисел
Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Теорема: наибольший общий делитель нескольких чисел a1, a2, …, ak равен числу dk, которое находится при последовательном вычислении НОД(a1, a2)=d2, НОД(d2, a3)=d3,
НОД(d3, a4)=d4, …, НОД(dk-1, ak)=dk.
Давайте разберемся, как выглядит процесс нахождения НОД нескольких чисел, рассмотрев решение примера.
Пример.
Найдите наибольший общий делитель четырех чисел 78, 294, 570 и 36.
Решение. В этом примере a1=78, a2=294, a3=570, a4=36.
Сначала по алгоритму Евклида определим наибольший общий делитель d2 двух первых чисел 78 и 294. При делении получаем равенства 294=78·3+60; 78=60·1+18; 60=18·3+6 и 18=6·3. Таким образом, d2=НОД(78, 294)=6.
Теперь вычислим d3=НОД(d2, a3)=НОД(6, 570). Опять применим алгоритм Евклида: 570=6·95, следовательно, d3=НОД(6, 570)=6.
Осталось вычислить d4=НОД(d3, a4)=НОД(6, 36). Так как 36 делится на 6, то d4=НОД(6, 36)=6.
Таким образом, наибольший общий делитель четырех данных чисел равен d4=6, то есть,
НОД(78, 294, 570, 36)=6.
Ответ: НОД(78, 294, 570, 36)=6.
Разложение чисел на простые множители также позволяет вычислять НОД трех и большего количества чисел. В этом случае наибольший общий делитель находится как произведение всех общих простых множителей данных чисел.
Пример.
Вычислите НОД чисел из предыдущего примера, используя их разложения на простые множители.
Решение.
Разложим числа 78, 294, 570 и 36 на простые множители, получаем 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2·3·3. Общими простыми множителями всех данных четырех чисел являются числа 2 и 3. Следовательно, НОД(78, 294, 570, 36)=2·3=6.
Ответ: НОД(78, 294, 570, 36)=6.
2.6. Нахождение НОД отрицательных чисел
Если одно, несколько или все числа, наибольший делитель которых нужно найти, являются отрицательными числами, то их НОД равен наибольшему общему делителю модулей этих чисел. Это связано с тем, что противоположные числа a и −a имеют одинаковые делители.
Пример.
Найдите НОД отрицательных целых чисел −231 и −140.
Решение.
Модуль числа −231 равен 231, а модуль числа −140 равен 140, и НОД(−231, −140) = НОД(231, 140). Алгоритм Евклида дает нам следующие равенства: 231=140·1+91; 140=91·1+49; 91=49·1+42; 49=42·1+7 и 42=7·6. Следовательно, НОД(231, 140)=7. Тогда искомый наибольший общий делитель отрицательных чисел −231 и −140 равен 7.
Ответ: НОД(−231, −140)=7.
Пример.
Определите НОД трех чисел −585, 81 и −189.
Решение.
При нахождении наибольшего общего делителя отрицательные числа можно заменить их абсолютными величинами, то есть, НОД(−585, 81, −189)=НОД(585, 81, 189). Разложения чисел 585, 81 и 189 на простые множители имеют соответственно вид 585=3·3·5·13, 81=3·3·3·3 и 189=3·3·3·7. Общими простыми множителями этих трех чисел являются 3 и 3. Тогда НОД(585, 81, 189)=3·3=9, следовательно, НОД(−585, 81, −189)=9.
Ответ: НОД(−585, 81, −189)=9.
Глава 3 Оценка эффективности применения алгоритмов
3.1. Сравнение алгоритмов Евклида вычитанием и делением.
Возьмем два числа: 112 и 32. Первое больше второго – присвоим ему остаток от деления 112 на 32. Теперь у нас имеются числа 16 и 32. Второе больше, поэтому присвоим ему остаток отделения 32 на 16, т. е. 0. Так выглядят эти действия в виде таблицы:
Начальные данные 112 32
Шаг 1 16 32
Шаг 2 16 0
А теперь снова, используя те же самые числа, составим таблицу, но на этот раз при помощи алгоритма вычитания.
Начальные данные 112 32
Шаг 1 80 32
Шаг 2 48 32
Шаг 3 16 32
Шаг 4 16 0
Из примера видно, что Алгоритм Евклида, реализуемый делением эффективней метода вычитания.
3.2. Сравнение алгоритмов вычисления НОД
Сравним алгоритмы вычисления НОД на двух примерах:
I. Сколько шагов потребуется, чтобы вычислить НОД (1980; 390)
1) алгоритм простого перебора – 360 шагов
2) алгоритм разложения на простые множители – 14 шагов
3) бинарный алгоритм Евклида – 4 шага
4) алгоритм Евклида – 2 шага
II. Найти НОД (20451; 3065)
1) алгоритм простого перебора – 6018 шагов
2) алгоритм разложения на простые множители – 25 шагов
3) бинарный алгоритм Евклида – 7 шагов
4) алгоритм Евклида – 7 шагов
Чтобы убедится в преимуществе приема последовательного деления над приемами разложения на простые множители, когда имеем дело с большими числами, рассмотрим следующий пример. Найти НОД (4847, 4181).
Разложение данных чисел на простые множители является делом нелегким, так как ни одно из чисел 2, 3, 4, 5, 6, 9, для которых устанавливаются в школе признаки делимости, не является делителем данных чисел. Алгоритм же Евклида легко и быстро приводит к результату: НОД (4847, 4181) = НОД(4181,666)=НОД(666,185)=НОД(185,111)=
НОД(111,74)=НОД(74,37)=37
Другой пример: сократить дробь
Решение. Выполним деление с остатком. Разделим 833 на 714:
833:714= 1(остаток 119)
Здесь делимое а = 833, делитель в = 714 и остаток r = 119.
НОД (833,714) = НОД (714, 119). Теперь разделим 714 :119=6, остаток 0. Таким образом, НОД (833 и 714) = 119. Тогда = .
Проведенное анкетирование показало, что большинство учителей знают алгоритм Евклида и знакомят учащихся с ним только на факультативах.
Список рекомендаций:
Нахождение НОД с помощью алгоритма Евклида не входит в общеобразовательную программу по математике, однако этот способ отыскания НОД следует показать в классе с преобладающим числом мотивированных учащихся.
Показать эффективность использования различных алгоритмов вычисления НОД чисел, из которых каждый ученик может выбрать те, которые показались ему целесообразными, и применять их на практике.
Полезно помнить, что НОД любого количества чисел не превосходит наименьшего из них.
Заключение.
В процессе проделанной работы в соответствии с ее целями и задачами были получены следующие выводы и результаты:
Для поиска НОД натуральных чисел существуют различные алгоритмы:
Если данные числа сравнительно невелики, то лучший алгоритм – непосредственный перебор.
Если числа достаточно большие, то нахождение НОД(а;b) путем перечисления всех делителей чисел а и b - процесс трудоемкий и ненадежный и тогда НОД(а;b) находится с помощью разложения чисел на простые множители. Этот алгоритм наиболее распространенный.
Алгоритм отыскания НОД(а, b) с помощью разложения чисел на простые множители прост, понятен и удобен, но у него есть существенный недостаток: если данные числа велики, да еще не очень легко раскладываются на множители, то задача отыскания НОД(а, b) становится довольно трудной. К тому же может оказаться, что, основательно потрудившись, мы убедимся, что НОД (а, b)=1 и вроде вся работа проделана зря.
Большинство древних алгоритмов со временем вытеснялось из вычислительной практики более новыми алгоритмами. Алгоритм Евклида избежал этой участи прежде всего благодаря своей экономности. Тем более удивительно, что хотя почтенный алгоритм Евклида и применяется в течение столь многих столетий, он не всегда является наилучшим способом для нахождения НОД!
Основной вывод, который мы сделали, состоит в том, что научиться быстро и правильно вычислять НОД чисел не так уж сложно. Вышеперечисленные алгоритмы рассчитаны на ум "обычного" человека и не требуют уникальных способностей. Главное - более или менее продолжительная тренировка.
В своей работе мы попытались показать эффективность использования различных алгоритмов вычисления НОД чисел, из которых каждый ученик может выбрать те, которые показались ему целесообразными, и применять их на практике. В будущем мы планируем продолжить исследование по данной теме и рассмотреть алгоритм Евклида для многочленов, при решении уравнений в целых числах.
Литература
[1].//Учебник для общеобразовательных учреждений Математика 6 класс под ред. Н.Я Зубаревой., Москва, Мнемозина,2013 г.
[2].//За страницами учебника алгебры. Л.Ф Пичурин, Москва, Просвещение, 1990г.
[3].//Сборник примеров и задач по математике, Н.А Терешин, Т.Н.Терешина Москва, Аквариум, 1997 г.
Интернет-ресурсы.
[1]. //Википедия (свободная энциклопедия), http://ru.wikipedia.org
[ 2]. //Сайт "Единая коллекция цифровых образовательных ресурсов".
[ 3]. // bymath.net — сайт «Вся элементарная математика», раздел «Общий делитель. Наибольший общий делитель»