Что такое нод видеоурок

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

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это способ часто удобен, но у него есть большой недостаток: разложить большое число на множители чрезвычайно трудно. Попробуйте найти, например, НОД(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 мм – такой квадрат будет единственный.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

НОД (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.

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

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

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

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;

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

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

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

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

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

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

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

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

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

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

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

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 секунд.

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

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

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

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

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

= = = = =

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

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

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

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

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

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

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

Источник