Исследовательский проект по математике: "Наибольший общий делитель и его практическое применение"

 

Наибольший общий делитель и

его практическое применение

г. Южа  2017

Оглавление

I теоретическая часть

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

1.1 актуальность

1.2.Цель работы и ее задачи…………………………………………………

1.3. гипотеза

2. Различные алгоритмы нахождения наибольшего общего делителя

    двух натуральных чисел………………………………………………………

2.1.Что такое НОД…………………………………………………………….

2.2. Свойства НОД…………………………………………………………….

2.3. Алгоритмы нахождения НОД двух и более чисел

3. Алгоритма Евклида и цепные дроби

II практическая часть

4. Исследования

4.1. Решение практических задач

4.2. Анкетирование учащихся 6-7 классов школы

5.     Выводы

6.     Заключение

7.     Литература

8.     Приложения

I теоретическая часть

Введение

Актуальность

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

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

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

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

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

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

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

3.                 Провести анкетирование «Знание и использование НОД »

4.                 Подобрать задачи на применение НОД

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

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

Гипотеза: Если есть алгоритмы, то есть их практическое применение.

Методы исследования: Изучение специальной литературы по данному вопросу: энциклопедии, справочники и учебные пособия. Анкетирование. Сравнение и анализ. Обработка полученных данных (составление обобщающих таблиц, диаграмм).

2. Различные алгоритмы нахождения наибольшего общего делителя   двух натуральных чисел.

2. 1. Что такое НОД двух чисел?

 В школьном учебнике математики дается такое определение: наибольшее натуральное число, на которое делятся без остатка числа a и  b, называют наибольшим общим делителем этих чисел.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел a или b не ноль.

Обозначения наибольшего общего делителя чисел a и b:   НОД(a; b).

2.2. Свойства наибольшего общего делителя.

Наибольший общий делитель обладает рядом свойств.

Перечислим основные  свойства наибольшего общего делителя (НОД).

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

1. Наибольший общий делитель чисел a и b равен наибольшему общему делителю чисел b и a, то есть, НОД(a; b)=НОД(b; a).

Это свойство НОД напрямую следует из определения наибольшего общего делителя.

2. Если a>b, то  НОД(a; b) = НОД(a – b; b).

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

3.Если a делится на b, то множество общих делителей чисел a и b совпадает с множеством делителей числа b, в частности, НОД(a;b)=b.

В частности, если числа a и b равны, то  НОД(а;b)=НОД(a;a)= НОД(b;b)=a=b. К примеру, НОД(132, 132)=132.

Данное свойство наибольшего делителя позволяет нам находить НОД двух чисел, когда одно из них делится на другое. При этом НОД равен одному из этих чисел, на которое делится другое число. Например, НОД(8, 24)=8, так как 24 кратно восьми.

4. Если a=b·q+c, где a, b, c и q – целые числа, то множество общих делителей чисел a и b совпадает с множеством общих делителей чисел b и c, в частности, НОД(a, b)=НОД(b, c).

5. Если m – любое натуральное число, то НОД(m·a, m·b)=m·НОД(a, b).

6. Пусть p – любой общий делитель чисел a и b, тогда НОД(a:p, b:p)= НОД(a, b):p, в частности, если p =НОД(a, b) имеем НОД (a:НОД(a, b), b : НОД(a, b))=1, то есть, числа a : НОД(a, b) и b:НОД(a, b) - взаимно простые.

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

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

2.3. Алгоритмы нахождения НОД двух и более чисел

1 алгоритм (следует из определения): Метод полного перебора для нахождения  наибольшего общего делителя (НОД)  натуральных чисел.

1. Выписываем все делители числа а;

2. Выписываем все делители числа b;

3. Выбираем среди них общие делители;

4. Среди общих делителей выбираем самое большое число – это и есть НОД(a, b).

Например:  Найти НОД(32;48).

Обозначим делители числа буквой D.                           

D (32) = {1; 2; 4; 8; 16; 32};

D (48) = {1; 2; 3; 4; 6; 8; 12; 16; 24; 48}.

          D (32; 48) = {1; 2; 4}.

НОД(32; 48) = 4.

    2 алгоритм : Метод перебора делителей меньшего числа для нахождения наибольшего общего делителя (НОД)  натуральных чисел.

1. Найти делители меньшего из данных чисел.

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

3. Записать найденное число – НОД.

Например:   Найти НОД(12;32).                              

D(12) = {1; 2; 3; 4; 6; 12}.

12 не является делителем числа 32;

6 не является делителем числа 32;

4- делитель 32.

НОД(12; 32) = 4.

Этот алгоритм легко реализуется, но его недостатком является то, что

необходимо проверять много вариантов. Это я показываю на примере нахождения НОД(195;156) (см. приложение 1).

3 алгоритм; Метод нахождения наибольшего общего делителя (НОД) натуральных чисел с помощью разложения на множители.

1. Находим разложение чисел на простые множители.

2. Подчеркиваем общие числа.

3. Находим произведение подчеркнутых чисел у одного числа.

4. Записываем ответ.

Например:

 Найти НОД(36; 48).    

36=2•2•3•3,

48=2•2•2•2•3.

НОД(36,48)=2•2•3=12

Это способ часто удобен, но у него есть большой недостаток: разложить большое число на множители чрезвычайно трудно. Попробуйте найти, например, НОД(54739; 205 757).

Есть сравнительно простой алгоритм нахождения общего делителя двух чисел. Его приписывают Евклиду, одному из величайших математиков древности. Евклид жил в III-II в до н.э. в Александрии, а по другим источникам, в Дамаске. Оставил несколько сочинений, известных в латинских и арабских переводах, наиболее значительное из которых – состоящие из 13 книг «Начала» («Elements»)- представляет собой систематическое изложение математики того времени.

4 алгоритм: Геометрический метод нахождения наибольшего общего делителя (НОД)  натуральных чисел с помощью квадратов.

Этот алгоритм – геометрическая иллюстрация алгоритма Евклида, описанного в 5-ем способе.

Например: Найти НОД(162;48).

Построим прямоугольник со сторонами 162мм и 48 мм.

От прямоугольника отрежем несколько квадратов со стороной 48 мм – таких квадратов три.

Остался прямоугольник со сторонами 48 мм и 162-3*48=18 мм.

От полученного прямоугольника снова отрезаем квадраты, у которых сторона равна 18 мм – таких квадратов получится два.

Остался прямоугольник со сторонами 18 мм и 48-2*18=12 мм.

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

Остался прямоугольник со сторонами 12 мм и 18-12=6 мм, который , в свою очередь состоит из двух квадратов 6мм х 6 мм.

Длина стороны последнего полученного квадрата и есть наибольший общий делитель чисел 162 и 48.

Ответ: НОД(162; 48)=6.

         Этот способ мне кажется нерациональным: вычерчивая прямоугольники и квадраты, легко ошибиться в построениях и получится неверный ответ. Но все же я попробовал решить этим способом несколько примеров нахождения наибольшего общего делителя двух натуральных чисел (см. приложение 2).

5 алгоритм: Алгоритм Евклида нахождения наибольшего общего делителя (НОД)  двух натуральных чисел вычитанием.

Древнегреческие математики называли этот алгоритм  ἀνθυφαίρεσις  или  ἀνταναίρεσις  — «взаимное вычитание». Этот алгоритм, видимо, не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

 1. Из большего числа вычитается меньшее.

 2.  Если получается 0, то числа равны друг другу и являются наибольшим  общим делителем.

  3.  Если результат вычитания не равен 0, то большее число заменяется на результат вычитания

  4.  Переход к пункту 1.

Например: Найти НОД(30; 18).                        

30 - 18 = 12;
18 - 12 = 6;
12 - 6 = 6;
6 – 6 = 0.

НОД – это уменьшаемое или вычитаемое.

НОД (30; 18) = 6.

Приведенный метод вычисления не является оптимальным. Например, для нахождения НОД(100; 2) следует выполнить 50 (!!) операций вычитания (см. приложение 1). Для ускорения вычисления НОД операцию вычитания следует заменить операцией взятия остатка от деления.

6 алгоритм:   Алгоритм Евклида нахождения наибольшего общего делителя (НОД)  двух натуральных чисел делением.

1. Большее число делится на меньшее

2. Если делится без остатка, то меньшее число и есть наибольший общий делитель.

3.  Если есть остаток, то большее число заменяем на остаток от деления.

4. Продолжаем деление до тех пор, пока не получим в остатке нуль. Последний неравный нулю остаток и есть НОД данных чисел.

Например: Найти НОД (273;1014).

Решение. Выполняем деление с остатком: По лемме:

1014=273*3+195                     

273=195*1+78                        

195=78*2+39                          

78=39*2                                          

НОД (273;1014) = НОД(195;273) = НОД(195;78) = НОД(78;39)= 39

НОД(273;1014)=39

7 алгоритм: Бинарный алгоритм Евклида нахождения наибольшего общего делителя (НОД)  двух натуральных чисел.

 Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД:

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

НОД(2a; 2b+1) = НОД(a; 2b+1),

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

Сам алгоритм выглядит так:

1.     Если a, b чётные, то НОД(a; b) = 2*НОД(a/2; b/2);

2.     Если a чётное, b нечётное, то НОД(a; b) = НОД(a/2; b);

3.     Если b чётное, a нечётное, то НОД(a; b) = НОД(a; b/2);

4.     Если a, b нечётные и b > a, то НОД(a; b) = НОД((b-a)/2; a);

5.     Если a, b нечётные и b < a, то НОД(a; b) = НОД((a-b)/2; b);

Например:

НОД(1978;2666)=2*НОД(989;1333)=2*НОД(989;344)=2*НОД(989;172)=2*НОД(989;86)=2*НОД(989;43)=2*НОД(946;43)=2*НОД(473;43)=2*НОД(430;43)= 2*НОД(215; 43)=2*НОД(172; 43)=2НОД*(86; 43)=2*НОД(43; 43)=2*43=86.

НОД(1978; 2666)=86

3. Алгоритма Евклида и цепные дроби

 3.1. Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Применяя к числам a и b алгоритм Евклида для определения их наибольшего общего делителя, получаем конечную систему равенств:

где неполным частным последовательных делений соответствуют остатки с условием b>>>…>>0, а соответствует остаток 0.

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

Скорее всего, она возникла из коммерческой практики древних купцов, когда им надо было сравнивать различные отношения целых чисел. Как, например, сравнивать отношения чисел 3703700 и 1234567 и чисел 22962965 и 7654321? Вполне естественна была попытка узнать, сколько раз меньшее число укладывается в большем. Легко проверить, что 3703700 = 2 · 1234567 + 1234566, а 22962965 = 3 · 7654321 + 2. Ясно теперь, что отношение 3703700 к 1234567 меньше, чем отношение 22962965 к 7654321. Таким образом, что сейчас мы записываем как

= 2,99999919 <= 3, 000000261,

Древние вычислители объясняли длинной фразой.

Если бы пришлось сравнить более близкие отношения чисел, например,  и , то вычисления были бы более сложными:

71755875 = 61735500 + 10020375;

61735500 = 6 · 10020375 + 1613250;

10020375 = 6 · 1613250 + 340875;

1613250 = 4 · 340875 + 249750;

340875 = 249750 + 91125;

249750 = 2 · 91125 + 67500;

91125 = 67500 + 23625;

67500 = 2 · 23625 + 20250;

23625 = 20250 + 3375;

20250 = 6 · 3375.

Алгоритм Евклида позволил определить НОД чисел 71755875 и 61735500, равный 3375, что соответствует разложению отношения 71755875 к 61735500 в цепную дробь:

 

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

Т.е. системе равенств (1) соответствует равносильная система

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

Такое выражение называется правильной (конечной) цепной или правильной непрерывной дробью, при этом предполагается, что – целое число, а , …,  - натуральные числа.

Имеются различные формы записи цепных дробей:

В самом деле, выражение

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

Сравнение > было выполнено в III в. до н.э. Аристархом Самосским в трактате «О расстоянии и размерах Луны и Солнца».

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

Дробь  представим в виде цепной дроби, данная дробь неправильная, заменяем смешанным числом, выделяем целую часть она равна 2. Далее найдем НОД (29;38) по алгоритму Евклида.

38:39=1·29+9

29:9=3·9+2

9:2=4·2+1

2:1=2·1

НОД (29;38)=1, тогда

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

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

3.2 Математическая проблема календаря

"День и ночь - сутки прочь", "Зима и лето - года нету": С незапамятных времён люди подметили, что важнейшие отрезки времени - год и сутки - определяются различными природными процессами.

Как сказано в одном старом учебнике космографии, «к сожалению, год не равен целому числу суток». С этим нельзя не согласиться, так как из упомянутого факта проистекает много неудобств. Зато он порождает интересную математическую проблему.

 

На рис. показана орбита Земля. 1 января 2016 ода в 0 часов Земля находилась в точке А. за 365 суток она не дойдёт до точки А и 1 января 2017 года в 0 часов окажется в точке В, а 1 января 12017  года – в точке С и т.д. Получится, что если отмечать положение Земли на орбите, соответствующие фиксированной дате, то оно будет каждый год иное: оно будет отставать почти на 6 часов. За 4 года отставание состоит почти сутки, и фиксированная дата будет попадать на разные времена года, т.е. 1 января с зимы постепенно переместится на осень, потом на лето. Т.е. в 1 году более 365, а именно 1 год = 365 суток 5 часов 48 минут 46 секунд=365,2421199 суток.

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

Выход из этого положения есть. Надо считать, что в некоторых годах по 365 суток, а в некоторых – по 366, чередуя годы так, чтобы средняя длина года была возможно ближе к истинной. Так можно воспроизвести истинную длину года с любой точностью, но для этого может понадобиться очень сложный закон чередования коротких (простых) и длинных (високосных) годов, что нежелательно. Нужен компромисс: сравнительно простой закон чередования коротких и длинных годов, дающий среднюю длину года, достаточно близкую к истиной.

 

Эту задачу впервые решил Юлий Цезарь. Точнее говоря, это сделал по его поручению александрийский астроном Созиген, вызванный для этой цели в Рим. Юлий Цезарь ввёл такую систему: три года подряд коротких (простых), четвёртый – длинный (високосный). Много позже, когда было  принято христианское летосчисление, високосными стали считать годы, номера которых делятся на 4.

Этот календарь называется юлианским. В России он существовал до февраля 1918 года. По юлианскому календарю средняя длина года равна 365  суток = 365 суток 6 часов.

Средняя длина юлианского года была больше истинной на 11 минут 14 секунд.

Юлианский календарь был улучшен папой Григорием ХIII. В 1582 году он произвёл следующую реформу календаря. Сохранил чередование простых и високосных лет, но добавил правило: если номер года оканчивается двумя нулями, а число сотен не делится на 4, то этот год простой, но 1600 - високосный. Кроме того, считая. Что от начала летосчисления (от «рождества Христова») уже накопилась ошибка в 10 дней, Григорий ХIII сразу прибавил 10 дней. С тех пор накопилось ещё 3 дня (в 1700,1800, 1900 годах). Он осуществил проект предложенный итальянским врачом и математиком Луиджи Лилио  Поэтому в настоящее время расхождение между юлианским и новым (григорианским) составляет 13 дней.

Какова средняя длина григорианского года? Из 400 лет по юлианскому календарю – 100 високосных. А по григорианскому – 97. Поэтому средняя длина григорианского года = 365 суток = 365,242500 суток = 365 суток 5 часов 49 минут 12 секунд, т.е. она больше истинной на 26 секунд.

Давайте взглянем  на проблему календаря с точки зрения теории цепных дробей. Целую часть опустим, так как наличие в каждом году 365 целых суток не требует напоминаний. 5 часов 48 минут 46 секунд что равно 20 926 секундам, а 1 сутки =86 400 секунд.

Находим НОД чисел 20 926 и 86 400 по алгоритму Евклида.

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

Первая подходящая дробь дает для длины года приближенное значение
 суток. Чтобы реализовать такую длину года, надо считать високосным 1 год из 4. Вторая дробь == соответствует такому решению: 7 високосных лет из каждых 29. Средняя длина года при этом получится 365 суток. Это точнее, чем 365, но зато сложнее.

Третья дробь==. Теперь за 33 года набегает «8» лишних лет и этот календарь в 1079 году был предложен персидским математиком и поэтом Омаром Хайямом. Он даже точнее Григорианского.

Следующая дробь 

=====

то получим  соответствующий ей календарь фантастической точности, по которому средняя длина года на 1 секунду будет превышать истинную! В1864 году профессор Дерптского университета (ныне Тартуский) Иоганн Генрих Медлер предложил с 20-го века ввести такой календарь в России. В нем пришлось бы каждые 128 лет пропускать 1 високосный  год, если високосные годы отсчитывать по принятой тогда юлианской системе. Процедура простая, но то ли в силу обычного консерватизма, то ли по другим причинам этот календарь распространения не получил.

Как видим, весьма простыми средствами достигнута очень большая точность.

Для данного алгоритма существует множество теоретических и практических применений. В частности он широко распространён в электронной коммерции. Также алгоритм используется при решении диофантовых уравнений (Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами). Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми, в честь древнегреческого математика Диофанта Александрийского. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел.

Долгое время алгоритм Евклида был самым эффективным способом отыскания наибольшего общего делителя, однако с появлением электронно-вычислительных машин ситуация изменилась Учет специфических особенностей выполнения арифметических операций компьютером позволил построить более эффективную (для программной реализации) версию алгоритма Евклида.

II практическая часть

4. Исследования

4.1.Решение практических задач

Задача 1.

Бабушка заготавливает на зиму компоты. Она кладёт в каждую банку одинаковое количество фруктов и ягод.  Сколько банок получилось, если понадобилось 48 груш, 60 яблок и 144 слив?

По сколько яблок, груш и слив в каждой банке?

Решение:

144 72 36 18 9 3 1

2 2 2 2 3 3

48 24 12 6 3 1

2 2 2 2 3

НОД (48; 60; 144) = 2 × 2 × 3 = 12

60 30 15 5 1

2 2 3 5

Ответ:  всего 12 банок, в каждой банке по 4 груши, по 5 яблок и по 12 слив.

 

Задача 2.

При составлении одинаковых праздничных букетов израсходовали 112 жёлтых  и 168 белых хризантем. Сколько букетов получилось? По сколько белых и жёлтых цветов в каждом букете?

Решение:

112 56 28 14 7 1

2 2 2 2 7

НОД (112; 168) = 2 × 2 × 2 × 7 = 56

168 84 42 21 7 1

2 2 2 3 7

Ответ:  всего 56 букетов, в каждом букете по 2 жёлтых и по 3 белых цветка.

Задача № 3

Имеется 60 апельсинов, 165 орехов и 225 конфет. Какое наибольшее число одинаковых новогодних подарков для детей можно сделать из этого запаса? Что войдёт в каждый набор?

 Решение:

Количество подарков должно быть делителем каждого из чисел, выражающих количество апельсинов, конфет и орехов, причем наибольшим из этих чисел. Поэтому надо найти НОД данных чисел.  НОД (60, 175, 225) = 15.  Каждый подарок будет содержать: 60 : 15 = 4 – апельсина,    175 : 15 = 11 – орехов и  225 : 15 = 15 – конфет.                                

Ответ: В одном подарке – 4 апельсина, 11 орехов, 15 конфет.

4.2. Анкетирование учащихся 6-7 классов школы

Анкета «Знание и использование НОД»

Дорогой друг!

Ответь, пожалуйста, на ряд несложных вопросов, это не займет много времени.

1. В каком классе ты учишься? ____________

2. Как расшифровывается: НОД _______

3.Если ты ответил хотя бы частично на 2 вопрос переходи к следующим, если

нет, можно сдать анкету.

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

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

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

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

4- другие способы

4. Используешь ли ты НОД при решении задач и упражнений по математике (алгебре, геометрии)?

5. Если на вопрос 5 ты ответил ДА, то укажи в каких случаях ты это делаешь:

1- сокращение дробей

2- решение задач

6.     Какие жизненные задачи ты можешь решить с помощью НОД?

5.Выводы

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

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

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

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

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

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

·                   НОД имеет практическое применение.

·                   С помощью алгоритма Евклида вычисляется наиболее точно длина года, но это трудно реализовать в календаре.

Считаю, что цель моей работы достигнута. Гипотеза подтверждена.

6. Заключение.

Математика – царица всех наук.

Ее возлюбленный – истина, ее наряд – простота и ясность.

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

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

                                                                                                        Снядецкий Ян

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

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

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

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

7.Список используемой литературы:

1.                 Виленкин Н.Я. и др. Математика, 6 класс: учебник для общеобразовательных учреждений. – М.: Мнемозина, 2013.- 288с.

2.                 Макарычев Ю.Н., Миндюк Н.Г. Алгебра: Дополнительные главы к школьному учебнику 8 кл.: учебное пособие для школ и классов с углубленным изучением математики.- М.:Просвещение,1996.- 207 с.

3.                 Пичурин Л.Ф. За страницами учебника алгебры- Москва: Просвещение, 1990г. -

4.                 Щетников А. И. Алгоритм Евклида и непрерывные дроби. - Новосибирск: АНТ, 2003 г.

http://www.rusnauka.com

Список используемых источников информации:

1. Википедия (свободная энциклопедия), http://ru.wikipedia.org

2. Сайт "Единая коллекция цифровых образовательных ресурсов".

3. http://www.rusnauka.com

Приложение 1

Задачи, решаемые на применение НОД

1. На приготовление японского блюда – суши израсходовано 140 г листовых морских водорослей, 210 г риса и 350 г рыбы . Сколько одинаковых ролов получилось? Ответ. 70                                        

2. На кружке мягкой игрушки ребята делали народные обереги куклы – мотанки из квадратных лоскутков ткани. Сколько куколок можно смотать из отреза ткани размером 48 см на 40 см без отходов? Какой наибольший размер лоскута для одной куклы? Ответ. 30 кукол, сторона 8 см.

3. На фабрике по переработке фруктов произвели 210 л виноградного сока , 126 л - апельсинового , 294 л ананасового. Сколько упаковок фруктового коктейля произвели из этих соков ? Каков состав коктейля? Ответ.42 у ., по 5 , 3 , 7 л соотв-но.

4. В зоошколе у панды Аси 12 одинаковых бамбуковых палочек, а у панды Юсси – 18 таких же. Сколько они могут составить многоугольников с наибольшим числом сторон так, чтобы были использованы все бамбуковые палочки? Ответ. 2 и 3 шестиугольника

5. На птицеферме вырастили птиц , занесенных в Красную Книгу Донбасса : 36 журавлей-красавок, 48 луговых тиркушек , 72 степных пустельг . Во сколько зоопарков можно отправить  этих птиц так , чтобы в каждый попало одинаковое количество птиц каждого вида? Ответ. 12

6. Во флористическую мастерскую поступили сухоцветы 156 ромашек , 234 васильков и 390 травинок. Мастера – флористы собрали из них больше 50 букетов разной формы, но при этом использовали одинаковое число сухоцветов каждого вида. Сколько букетов сделано? Сколько цветов каждого вида в одном букете? Ответ. 13 бук., по 12, 18, 30 соотв-но.

7. На городской смотр детских театров прибыло 145 мальчиков и 87 девочек. В каждой театральной группе одинаковое число мальчиков и одинаковое число девочек. Сколько групп юных артистов участвовало в творческом смотре? Сколько мальчиков и сколько девочек было в каждой группе? Ответ.29ком . по 5 м. и 3д.

8. Решить уравнение : НОД(а;8)=4. Ответ. 2к-1, к-натур.

9. Садовый участок размером 54 м на 48 м по периметру оградили забором. Для этого через равные промежутки установили столбы для крепления забора. Сколько столбов установили и на каком максимальном  расстоянии друг от друга? Ответ.34 ст. , 6 м

10. В наборе 185 бусинок лилового цвета и 111 бусинок бирюзового. Сколько  браслетов для кукол можно сплести из одинакового числа  бусин каждого цвета? Сколько бусин каждого цвета в браслете?  Ответ.37 бр. , по 5 и 3 бус.

11. Во всех новогодних подарках было 185 конфет – сюрпризов и 111 маленьких игрушек. Сколько одинаковых подарков было? Ответ.37

12. На летний отдых в один туристический лагерь поехали 424 школьника , а в другой -477.  Сколько автобусов с одинаковым числом мест в каждом было заказано? Причем все места были заняты , и никто не стоял. Сколько мест в каждом автобусе? Ответ. 17 авт. по 53 пас.

13. Для изготовления поделок из природного материала было использовано 36 желудей, 48 орехов и 72 сухих веточек . Какое наибольшее число разных поделок можно сделать из одинакового числа каждого вида материала? Ответ. 12

14. В конкурсе участнику предложили положить в волшебные сундучки 18 жемчужин и 24 кристалла по одинаковому количеству в каждый. Сколько сундучков было заполнено? Овет.6

15. Стол размером 195см на 156 см  решили декорировать разноцветными квадратными плитками. Каковы наибольшие размеры плитки? Сколько плиток надо? Ответ.20 пл. по39 на 39.

16. В сувенирный магазин привезли 36 ракушек одного вида , 48 –другого и 72 третьего. Какое наибольшее число одинаковых наборов ракушек можно сделать? Ответ.12

17. Выпускники школы в День знаний сделали подарки первоклассникам.  Для этого приготовили 69 карандашей и 46 ластиков-смайликов и  раздали малышам поровну каждому. Сколько учеников в первом классе? Ответ.23