Гипермаркет знаний>>Информатика>>Информатика 9 класс. Полные уроки>>Информатика: Алгоритм Евклида.

Тема

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

Цель

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

Ход урока

Понятие Алгоритм Евклида

Алгоритм Евклида является одним из древнейших математических формул, которой уже более 2000 лет.

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

К середине XVI века этот алгоритм был распространён на многочлены: от одного переменного в дальнейшем удалось определить алгоритм Евклида для других алгебраических объектов.

Также, алгоритм Евклида является средством для представления рационального числа в виде цепной дроби, что часто используется в программах для ЭВМ.

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

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

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

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

Алгоритм нахождения НОД делением

Описание алгоритма нахождения наибольшего общего делителя делением

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

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

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

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

Пример:

Найти наибольший общий делитель для 300 и 180.

300/180 = 1 (остаток 120)

180/120 = 1 (остаток 60)

120/60 = 2 (остаток 0).

Конец: наибольший общий делитель – это 6.

В цикле «a» или «b» фиксируется остаток от деления. Когда остатка нет (мы не знаем в «а» он или «b,» поэтому проверяем оба условия), то цикл завершается.

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

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

Описание алгоритма нахождения наибольшего общего делителя вычитанием

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

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

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

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

Пример: Найти для чисел 300 и 180.

300 - 180 = 120

180 - 120 = 60

120 - 60 = 60

60 – 60 = 0

Конец: Наиболее общий делитель чисел 300 и 180 – 60.

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

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

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

Если отрезки a иb соизмерыми, то последний не нулевой остаток даст наибольшую общую меру отрезков.

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

Пример:

В качестве отрезков возьмём сторону AB и AC равнобедренного треугольника ABC, у которого A=C = 72°, B= 36°.

В качестве первого остатка мы получим отрезок AD (CD-биссектриса угла C), и, как легко видеть, последовательность и нулевых остатков будет бесконечной.

Значит, отрезки AB и AC не соизмеримы.

Вопросы

1. Что представляет собой алгоритм Евклида?

2. Что такое наибольший общий делитель?

Список использованных источников

1. Урок на тему: «Алгоритм Эвклида», Корчевой П. И., г. Луцк

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

3. Коунтинхо С. Введение в теорию чисел. Алгоритм RSA, – М., 2001 г.

4. Кострикин А.И. Введение в алгебру, – М., 2000 г.

Отредактировано и выслано преподавателем Киевского национального университета им. Тараса Шевченко Соловьевым М. С.

Над уроком работали

Корчевой П. И.

Соловьев М. С.

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