Исследовательская работа «О чем молчит НОД»

Оглавление

Введение                                                                                                                                        3

Глава 1.   «Прадедушка» всех алгоритмов                                                                                 5

Глава 2.   Алгоритмы  вычисления НОД                                                                                   

2.1. Алгоритм  простого перебора                                                                                               6

2.2. Алгоритм  разложения на множители                                                                                  6

2.3. Алгоритм Евклида                                                                                                                  7

2.4. Бинарный алгоритм Евклида.                                                                                                7

2.5. Вычисление НОД трех и более чисел.                                                                                  8

2.6. Нахождение НОД отрицательных чисел                                                                              9

Глава 3 Оценка эффективности применения алгоритмов               

3.1. Сравнение алгоритмов Евклида вычитанием и делением.                                              10

3.2. Сравнение алгоритмов вычисления НОД                                                                          10

Заключение                                                                                                                                   12

Литература                                                                                                                                    13

Приложение 1                                                                                                                               14

Приложение 2                                                                                                                               15

Введение.

Мы с вами, можем удивляться, узнав, что всю жизнь мы исполняем огромное число всякого рода алгоритмов.

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

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

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

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

Данная работа знакомит с алгоритмами вычисления НОД. Знакомство с ними не только дополняет и углубляет знания, но и развивает интерес к предмету, любознательность и логическое мышление. Предлагаемая работа рассчитана на учеников, желающих повысить уровень математической подготовки, увидеть красоту математических выкладок и эстетику алгоритма Евклида, а так же помочь учащимся не бояться громоздких и очень трудных с виду задач с НОД, помня пословицу: «Волков бояться, в лес не ходить!».

Гипотеза: Если алгоритм Евклида является удобным и быстрым способом вычисления НОД, то нужно знакомить с ним учащихся и чаще использовать.

Цель исследования: изучить разные алгоритмы вычисления НОД, выявить наиболее рациональные способы решения, красиво и сравнительно просто приводящие к ответу.

Достижение поставленной цели требует решения следующих основных задач:

1.      Рассмотреть несколько алгоритмов вычисления НОД

2.      Сравнить алгоритмы вычисления НОД

3.      Провести анкетирование

4.      Составить список рекомендаций

Предмет исследования: Алгоритмы вычисления НОД

Объект исследования: умения и навыки вычисления НОД

Методы исследования:

·         Изучение специальной литературы по данному вопросу: энциклопедии, справочники и учебные пособия.

·         Анкетирование.

·         Сравнение и анализ.

·         Обработка полученных данных (составление обобщающих таблиц, диаграмм)

·         Работа в компьютерных программах 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.

Пример:

 Найти НОД для 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 <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. Нахождение НОД трех и большего количества чисел

 Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Теорема: наибольший общий делитель нескольких чисел a₁, a₂, …, a_k равен числу d_k, которое находится при последовательном вычислении НОД(a₁, a₂)=d₂, НОД(d₂, a₃)=d₃,

НОД(d₃, a₄)=d₄, …, НОД(d_k-1, a_k)=d_k.

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

Пример.

 Найдите наибольший общий делитель четырех чисел 78, 294, 570 и 36.

Решение.   В этом примере a₁=78, a₂=294, a₃=570, a₄=36.

 Сначала по алгоритму Евклида определим наибольший общий делитель d₂ двух первых чисел 78 и 294. При делении получаем равенства 294=78·3+60; 78=60·1+18; 60=18·3+6 и 18=6·3. Таким образом, d₂=НОД(78, 294)=6.

 Теперь вычислим d₃=НОД(d₂, a₃)=НОД(6, 570). Опять применим алгоритм Евклида: 570=6·95, следовательно, d₃=НОД(6, 570)=6.

 Осталось вычислить d₄=НОД(d₃, a₄)=НОД(6, 36). Так как 36 делится на 6, то d₄=НОД(6, 36)=6.

 Таким образом, наибольший общий делитель четырех данных чисел равен d₄=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

714     1

119

Здесь делимое  а = 833, делитель в = 714 и остаток  r  = 119.

НОД (833,714) = НОД (714, 119). Теперь разделим 714 на 119:

714            119

             714      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 — сайт «Вся элементарная математика», раздел «Общий делитель. Наибольший общий делитель»

Приложение 1

   Каждый из нас в школе изучал, что такое наибольший общий делитель (далее НОД) двух чисел a и b. Конечно же, это наибольшее целое число d, на которое a и b делятся без остатка. Без труда каждый ученик может сказать, например, что НОД(12, 18) = 6. Но что если одно из чисел равно 0? А если a или b отрицательно? Над этим вопросом на школьных уроках, наверное, не каждый из нас задумывался. Для того чтобы ответить на поставленные вопросы, приведем определение – что же такое наибольший общий делитель.

   Определение 1. Наибольшим общим делителем (далее НОД) двух целых чисел a и b, одновременно не равных нулю, называется такое наибольшее целое число d, на которое a и b делятся без остатка. Этот факт обозначается так: d = НОД(a, b). Если оба числа равны нулю, то положим НОД(0, 0) = 0.

   Исходя из определения, имеют место следующие равенства:

   НОД(a, b) = НОД(b, a),

   НОД(a, b) = НОД(-a, b)

   НОД(a, 0) = |a|

Приложение 2.

      Анкета

Уважаемый респондент! Мы, ученица 6В класса и учитель математики МОУ «СОШ №7», просим Вас принять участие в анкетировании учителей математики. Ответьте, пожалуйста, на ряд несложных вопросов, это не займет много времени. Для правильного заполнения анкеты достаточно поставить галочку или обвести вариант ответа, наиболее точно соответствующий вашему мнению. Благодарим за внимание.

6. Возникала ли на уроках проблема экономии

  времени при вычислении НОД

1 - да

2 – нет

3 – иногда

Муниципальная учебно-исследовательская

конференция школьников

«Юный исследователь»

Направление математика

О чем молчит НОД

Исследовательская работа

                                                                                      Выполнена ученицей 6 «в» класса

                                                                            МОУ «Средняя общеобразовательная

                                                           Школа № 7», МО «Котлас»,

                                                     Архангельской области

                                                                    Афанасьевой Еленой Игоревной

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

                                                                               МОУ «Средняя общеобразовательная

                                                              школа № 7», МО «Котлас»,

                                                        Архангельской области

                                                                Ямчук Наталья Григорьевна

г. Котлас, 2014