Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Исследовательская работа «О чем молчит НОД»
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 24 мая.

Подать заявку на курс
  • Математика

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

Выбранный для просмотра документ Выступление.docx

библиотека
материалов

Название работы –

О чём молчит

НОД










Данная работа знакомит с

алгоритмами

вычисления НОД




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




Цель исследования:

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


Цель исследования:

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


Основные задачи:

  • Рассмотреть несколько

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

  • Сравнить алгоритмы

вычисления НОД

  • Провести анкетирование

  • Составить список

рекомендаций


Мы рассмотрели:

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

Нахождение НОД разложением чисел на простые множ-ли

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

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

Нахождение НОД трех и большего количества чисел

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

Алгоритм Евклида эффективный алгоритм для нахождения

наибольшего общего делителя двух целых чисел.

Алгоритм назван в честь греческого математика Евклида,

который впервые описал его.


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

вычитанием: Найти НОД для 30 и 18. 30 - 18 = 12 18 - 12 = 6

12 - 6 = 6

6 – 6 = 0

Делением НОД(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


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

Основан на свойствах:

НОД(2n, 2m) = 2 НОД(n, m)

НОД(2n, 2m+1) = НОД(n, 2m+1)

НОД(-n, m) = НОД(n, m)


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

Результаты:

С алгоритмом Евклида знакомы;

Используют только на

факультативах


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

Начальные данные 112 32

Шаг 1 16 32

Шаг 2 16 0

Начальные данные 112 32

Шаг 1 80 32

Шаг 2 48 32

Шаг 3 16 32

Шаг 4 16 0


Сравним алгоритмы вычисления

НОД на примере:

Сколько шагов потребуется, чтобы

вычислить НОД (1980; 390)

1) алгоритм простого перебора – 360 шагов

2) алгоритм разложения на простые

множители – 14 шагов

3) бинарный алгоритм Евклида – 4 шага

4) алгоритм Евклида – 2 шага


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

Найти НОД (4847, 4181).

НОД (4847, 4181) = НОД(4181,666)=НОД(666,185)=НОД(185,111)=

НОД(111,74)=НОД(74,37)=37


Ещё один пример: сократить дробь 714/833

С помощью алгоритма Евклида найти Нод можно быстро, а разложение займет больше времени.

ВЫВОД 1

  • Если данные числа сравнительно невелики, то лучший алгоритм – непосредственный перебор.








Если числа достаточно большие, то нахождение НОД(а;b) путем перечисления всех делителей чисел а и b - процесс трудоемкий и ненадежный и тогда НОД(а;b) находится с помощью разложения чисел на простые множители. Этот алгоритм наиболее распространенный.


Алгоритм отыскания НОД(а, b) с помощью разложения чисел на простые множители прост, понятен и удобен, но у него есть существенный недостаток: если данные числа велики, да еще не очень легко раскладываются на множители, то задача отыскания НОД(а, b) становится довольно трудной. К тому же может оказаться, что, основательно потрудившись, мы убедимся, что НОД (а, b)=1 и вроде вся работа проделана зря.


Большинство древних алгоритмов со временем вытеснялось из вычислительной практики более новыми алгоритмами. Алгоритм Евклида избежал этой участи прежде всего благодаря своей экономности. Тем более удивительно, что хотя почтенный алгоритм Евклида и применяется в течение столь многих столетий, он не всегда является наилучшим способом для нахождения НОД!


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






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


ЗАКОНЧИТЬ СВОЁ ВЫСТУПЛЕНИЕ Я ХОЧУ СЛОВАМИ

«Математика – царица всех наук. Ее возлюбленный – истина, ее наряд – простота и ясность. Дворец этой владычицы окружен тернистыми зарослями, и, чтобы достичь его, каждому приходится продираться сквозь чащу. Случайный путник не обнаружит во дворце ничего привлекательного. Красота его открывается лишь разуму, любящему истину, закаленному в борьбе с трудностями, свидетельствующему о незаурядности и непреодолимой склонности человека к необычайно запутанным, но неиссякаемым и возвышенным наслаждениям ума, свойственным самой природе людей» (Снядецкий Ян)



Выбранный для просмотра документ Юный исследователь 2014.docx

библиотека
материалов

hello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_m2a7690f7.gifhello_html_7ccaa051.gifhello_html_56a094b7.gifhello_html_56a094b7.gifОглавление

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

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

Другой пример: сократить дробь hello_html_m35dbb61b.gif.

Решение. Выполним деление с остатком. Разделим 833 на 714:

  1. 714

714 1

119

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

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

  1. 119

714 6

0 Таким образом, НОД (833 и 714) = 119. Тогда hello_html_m35dbb61b.gif = hello_html_72e75332.gif = hello_html_mdcbf3df.gif!

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

Список рекомендаций:

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

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

  • Полезно помнить, что НОД любого количества чисел не превосходит наименьшего из них.

  • Усвоение алгоритма нахождения НОД позволит им в дальнейшем успешно сокращать дроби, а также находить НОК по формуле:

НОК (а;hello_html_mf43c4b8.gif)=





Заключение.

В процессе проделанной работы в соответствии с ее целями и задачами были получены следующие выводы и результаты:

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

  • Если данные числа сравнительно невелики, то лучший алгоритм – непосредственный перебор.

  • Если числа достаточно большие, то нахождение НОД(а;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», просим Вас принять участие в анкетировании учителей математики. Ответьте, пожалуйста, на ряд несложных вопросов, это не займет много времени. Для правильного заполнения анкеты достаточно поставить галочку или обвести вариант ответа, наиболее точно соответствующий вашему мнению. Благодарим за внимание.

1. Ваш стаж работы:

1 – до 5 лет;

2 – до 10 лет;

3 – до 15 лет;

4 – до 20 лет;

5 – 20лет и более.


2. Как на Ваш взгляд преподаватель влияет на отношение учащихся к математике?

1 – профессионально подготовленный преподаватель прививает огромный интерес к предмету; и, наоборот, скучный преподаватель отбивает всякий интерес от изучения предмета;

2 – профессионализм преподавателя не влияет на личностное отношение учащихся к предмету.





3. Какие способы вычисления НОД ВЫ используете на своих уроках

1 – перебор всех делителей

2 – разложение на множители

3 – другие способы

4. Знаете ли ВЫ об алгоритме Евклида для вычисления НОД

1знаю;

2 – не знаю;


5. Знакомили ли ВЫ своих учеников с алгоритмом Евклида

1 – на уроках

2 – нет;

3 – на факультативах;



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

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

1 - да

2 – нет

3 – иногда


Выбранный для просмотра документ о чем молчит нод.ppt

библиотека
материалов
Выполнена ученицей 6 «в» класса МОУ «Средняя общеобразовательная Школа № 7»,...
 Данная работа знакомит с алгоритмами вычисления НОД
Гипотеза: Если алгоритм Евклида является удобным и быстрым способом вычислени...
Цель исследования: изучить разные алгоритмы вычисления НОД, выявить наиболее...
Основные задачи: Рассмотреть несколько алгоритмов вычисления НОД Сравнить алг...
Алгоритм простого перебора Нахождение НОД с помощью разложения чисел на прост...
Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего дел...
Алгоритма Евклида вычитанием: делением: Найти НОД для 30 и 18. 30 - 18 = 12 1...
Бинарный алгоритм Евклида. НОД(2n, 2m) = 2 НОД(n, m) НОД(2n, 2m+1) = НОД(n, 2...
Мы провели анкетирование учителей, чтобы выяснить, как часто используется ал...
Сравнение алгоритмов Евклида вычитанием и делением. Начальные данные 112	32 Ш...
Сравним алгоритмы вычисления НОД на примере: Сколько шагов потребуется, чтобы...
Чтобы убедится в преимуществе приема последовательного деления над приемами р...
сократить дробь . 833 714 119 714 1 714 714 119 6 0 714 833 Таким образом, НО...
Если данные числа сравнительно невелики, то лучший алгоритм – непосредственн...
Основной вывод, который мы сделали, состоит в том, что научиться быстро и пра...
«Математика – царица всех наук. Ее возлюбленный – истина, ее наряд – простота...
Литература [1].//Учебник для общеобразовательных учреждений Математика 6 кла...
19 1

Описание презентации по отдельным слайдам:

№ слайда 1 Выполнена ученицей 6 «в» класса МОУ «Средняя общеобразовательная Школа № 7»,
Описание слайда:

Выполнена ученицей 6 «в» класса МОУ «Средняя общеобразовательная Школа № 7», МО «Котлас», Архангельской области Афанасьевой Еленой Игоревной

№ слайда 2  Данная работа знакомит с алгоритмами вычисления НОД
Описание слайда:

Данная работа знакомит с алгоритмами вычисления НОД

№ слайда 3 Гипотеза: Если алгоритм Евклида является удобным и быстрым способом вычислени
Описание слайда:

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

№ слайда 4 Цель исследования: изучить разные алгоритмы вычисления НОД, выявить наиболее
Описание слайда:

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

№ слайда 5 Основные задачи: Рассмотреть несколько алгоритмов вычисления НОД Сравнить алг
Описание слайда:

Основные задачи: Рассмотреть несколько алгоритмов вычисления НОД Сравнить алгоритмы вычисления НОД Провести анкетирование Составить список рекомендаций

№ слайда 6 Алгоритм простого перебора Нахождение НОД с помощью разложения чисел на прост
Описание слайда:

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

№ слайда 7 Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего дел
Описание слайда:

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

№ слайда 8 Алгоритма Евклида вычитанием: делением: Найти НОД для 30 и 18. 30 - 18 = 12 1
Описание слайда:

Алгоритма Евклида вычитанием: делением: Найти НОД для 30 и 18. 30 - 18 = 12 18 - 12 = 6 12 - 6 = 6 6 – 6 = 0 НОД(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

№ слайда 9 Бинарный алгоритм Евклида. НОД(2n, 2m) = 2 НОД(n, m) НОД(2n, 2m+1) = НОД(n, 2
Описание слайда:

Бинарный алгоритм Евклида. НОД(2n, 2m) = 2 НОД(n, m) НОД(2n, 2m+1) = НОД(n, 2m+1) НОД(-n, m) = НОД(n, m)

№ слайда 10 Мы провели анкетирование учителей, чтобы выяснить, как часто используется ал
Описание слайда:

Мы провели анкетирование учителей, чтобы выяснить, как часто используется алгоритм Евклида. Результаты: С алгоритмом Евклида знакомы; Используют только на факультативах

№ слайда 11 Сравнение алгоритмов Евклида вычитанием и делением. Начальные данные 112	32 Ш
Описание слайда:

Сравнение алгоритмов Евклида вычитанием и делением. Начальные данные 112 32 Шаг 1 16 32 Шаг 2 16 0 Начальные данные 112 32 Шаг 1 80 32 Шаг 2 48 32 Шаг 3 16 32 Шаг 4 16 0

№ слайда 12 Сравним алгоритмы вычисления НОД на примере: Сколько шагов потребуется, чтобы
Описание слайда:

Сравним алгоритмы вычисления НОД на примере: Сколько шагов потребуется, чтобы вычислить НОД (1980; 390) 1) алгоритм простого перебора – 360 шагов 2) алгоритм разложения на простые множители – 14 шагов 3) бинарный алгоритм Евклида – 4 шага 4) алгоритм Евклида – 2 шага

№ слайда 13 Чтобы убедится в преимуществе приема последовательного деления над приемами р
Описание слайда:

Чтобы убедится в преимуществе приема последовательного деления над приемами разложения на простые множители, когда имеем дело с большими числами, рассмотрим следующий пример. Найти НОД (4847, 4181). НОД (4847, 4181) = НОД(4181,666)=НОД(666,185)=НОД(185,111)= НОД(111,74)=НОД(74,37)=37

№ слайда 14 сократить дробь . 833 714 119 714 1 714 714 119 6 0 714 833 Таким образом, НО
Описание слайда:

сократить дробь . 833 714 119 714 1 714 714 119 6 0 714 833 Таким образом, НОД (833;714) = 119. Тогда 714 833 = 6 7

№ слайда 15 Если данные числа сравнительно невелики, то лучший алгоритм – непосредственн
Описание слайда:

Если данные числа сравнительно невелики, то лучший алгоритм – непосредственный перебор. Если числа достаточно большие, то нахождение НОД(а;b) путем перечисления всех делителей чисел а и b - процесс трудоемкий и ненадежный и тогда НОД(а;b) находится с помощью разложения чисел на простые множители. Этот алгоритм наиболее распространенный. Алгоритм отыскания НОД(а, b) с помощью разложения чисел на простые множители прост, понятен и удобен, но у него есть существенный недостаток: если данные числа велики, да еще не очень легко раскладываются на множители, то задача отыскания НОД(а, b) становится довольно трудной. К тому же может оказаться, что, основательно потрудившись, мы убедимся, что НОД (а, b)=1 и вроде вся работа проделана зря. Большинство древних алгоритмов со временем вытеснялось из вычислительной практики более новыми алгоритмами. Алгоритм Евклида избежал этой участи прежде всего благодаря своей экономности. Тем более удивительно, что хотя почтенный алгоритм Евклида и применяется в течение столь многих столетий, он не всегда является наилучшим способом для нахождения НОД!

№ слайда 16 Основной вывод, который мы сделали, состоит в том, что научиться быстро и пра
Описание слайда:

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

№ слайда 17 «Математика – царица всех наук. Ее возлюбленный – истина, ее наряд – простота
Описание слайда:

«Математика – царица всех наук. Ее возлюбленный – истина, ее наряд – простота и ясность. Дворец этой владычицы окружен тернистыми зарослями, и, чтобы достичь его, каждому приходится продираться сквозь чащу. Случайный путник не обнаружит во дворце ничего привлекательного. Красота его открывается лишь разуму, любящему истину, закаленному в борьбе с трудностями, свидетельствующему о незаурядности и непреодолимой склонности человека к необычайно запутанным, но неиссякаемым и возвышенным наслаждениям ума, свойственным самой природе людей» Снядецкий Ян

№ слайда 18 Литература [1].//Учебник для общеобразовательных учреждений Математика 6 кла
Описание слайда:

Литература [1].//Учебник для общеобразовательных учреждений Математика 6 класс под ред. Н.Я Зубаревой., Москва, Мнемозина,2013 г. [2].//За страницами учебника алгебры. Л.Ф Пичурин, Москва, Просвещение, 1990г. [3].//Сборник примеров и задач по математике, Н.А Терешин, Т.Н.Терешина Москва, Аквариум, 1997 г. Интернет-ресурсы. [1]. //Википедия (свободная энциклопедия), http://ru.wikipedia.org [ 2]. //Сайт "Единая коллекция цифровых образовательных ресурсов". [ 3]. // bymath.net — сайт «Вся элементарная математика», раздел «Общий делитель. Наибольший общий делитель»

№ слайда 19
Описание слайда:

Выбранный для просмотра документ титульный лист.doc

библиотека
материалов

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

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

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



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







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

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









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

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

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

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

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



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

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

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

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

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



г. Котлас, 2014

Краткое описание документа:

В этой исследовательской работе рассмотрены разные алгоритмы вычисления наибольшего общего делителя целых чисел, нахождение НОД отрицательных чисел, трех и более чисел. Особое внимание уделено алгоритму Евклида. Проказано действие алгоритмов на примерах. Проведено сравнение алгоритма Евклида вычитанием и делением. С помощью компьюторной программы определено количество шагов при различных способах подсчёта наибольшего общего делителя. Есть гипотеза, методы исследования, объект.В заключении сделаны выводы. Проведено антекирование учителей.Презентация. Карточки для выступления.
Автор
Дата добавления 26.04.2014
Раздел Математика
Подраздел Другие методич. материалы
Просмотров1001
Номер материала 85001042627
Получить свидетельство о публикации

Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Похожие материалы

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