<metakeywords>Информатика, класс, урок, на тему, 9 класс, Алгоритм Евклида.</metakeywords>
<metakeywords>Информатика, класс, урок, на тему, 9 класс, Алгоритм Евклида.</metakeywords>
-
'''Тема: Алгоритм Евклида'''.
+
== Тема ==
-
'''Цель: '''Ознакомить с понятием «алгоритм Евклида».Научить находить наиболее общие делители разными математическими способами.
+
*'''Алгоритм Евклида'''
-
<br>
+
== Цель ==
-
'''Алгоритм Евклида''' является одним из древнейших математических формул, которой уже более 2000 лет.
+
*Ознакомить с понятием «алгоритм Евклида».
+
*Научить находить наиболее общие делители разными математическими способами.
-
Алгоритм сформулирован в “Началах” Евклида, где из него выводятся свойства простых чисел и наименьшее общее кратное.
+
== Ход урока ==
-
К середине XVI века этот алгоритм был распространён на многочлены: от одного переменного в дальнейшем удалось определить алгоритм Евклида для других алгебраических объектов.
+
=== Понятие Алгоритм Евклида ===
-
[[Image:Euclid 2.jpg]]
+
'''[[Алгоритм Евклида|Алгоритм Евклида]]''' является одним из древнейших математических '''[[Стаття на тему: Внесення формул і функцій у комірки. Абсолютна та відносна адресація|формул]]''', которой уже более 2000 лет.
+
+
'''[[Определение и свойства алгоритма. Полные уроки|Алгоритм]]''' сформулирован в “Началах” Евклида, где из него выводятся свойства простых чисел и наименьшее общее кратное.
+
+
К середине XVI века этот '''[[Определение и свойства алгоритма|алгоритм]]''' был распространён на многочлены: от одного переменного в дальнейшем удалось определить алгоритм Евклида для других алгебраических объектов.
+
+
+
+
[[Image:Euclid 2.jpg|240px|Евклид]]
<br>
<br>
-
Также, алгоритм Евклида является средством для представления рационального числа в виде цепной дроби, что часто используется в программах для ЭВМ.
+
Также, алгоритм Евклида является средством для представления рационального числа в виде цепной дроби, что часто используется в программах для '''[[История ЭВМ. Полные уроки|ЭВМ]]'''.
Алгоритм Евклида придуман для нахождения ''наибольшего общего делителя'' пары целых чисел.
Алгоритм Евклида придуман для нахождения ''наибольшего общего делителя'' пары целых чисел.
+
+
{{#ev:youtube|19DWiE1bErA}}
{{#ev:youtube|19DWiE1bErA}}
<br>
<br>
+
+
=== Наибольший общий делитель ===
'''Наибольший общий делитель''' (НОД) – это число, делящее без остатка два числа и делится само без остатка на любой другой делитель данных чисел.
'''Наибольший общий делитель''' (НОД) – это число, делящее без остатка два числа и делится само без остатка на любой другой делитель данных чисел.
Строка 33:
Строка 46:
<br>
<br>
-
[[Image:Gcd.jpg]]
+
[[Image:Gcd.jpg|480px|Алгоритм Евклида]]
<br>
<br>
-
<u>Описание алгоритма нахождения наибольшего общего делителя делением </u>
+
=== Алгоритм нахождения НОД делением ===
+
+
'''Описание алгоритма нахождения наибольшего общего делителя делением '''
- Большее число делится на меньшее
- Большее число делится на меньшее
-
- Если делится без остатка, то меньшее число и есть наибольший общий делитель. Теперь нужно выйти из цикла
+
- Если делится без остатка, то меньшее число и есть наибольший общий делитель. Теперь нужно выйти из '''[[Цикли. Блок–схеми алгоритмів з циклами|цикла]]'''
- Если есть остаток, то большее число заменяем на остаток от деления
- Если есть остаток, то большее число заменяем на остаток от деления
Строка 63:
Строка 78:
<br>
<br>
-
В цикле «a» или «b» фиксируется остаток от деления. Когда остатка нет (мы не знаем в «а» он или «b,» поэтому проверяем оба условия), то цикл завершается.
+
В '''[[Циклические алгоритмы. Полные уроки|цикле]]''' «a» или «b» фиксируется остаток от деления. Когда остатка нет (мы не знаем в «а» он или «b,» поэтому проверяем оба '''[[Условия выбора и простые логические выражения|условия]]'''), то цикл завершается.
В конце выводится сумма «a» и «b», потому что мы не знаем, в какой переменной записан наибольший общий делитель, а в одной из них в любом случае 0, не влияющий на результат суммы.
В конце выводится сумма «a» и «b», потому что мы не знаем, в какой переменной записан наибольший общий делитель, а в одной из них в любом случае 0, не влияющий на результат суммы.
Строка 73:
Строка 88:
<br>
<br>
-
<u>Описание алгоритма нахождения наибольшего общего делителя вычитанием </u>
+
=== Алгоритм нахождения НОД вычитанием ===
+
+
'''Описание [[Циклические алгоритмы|алгоритма]] нахождения наибольшего общего делителя вычитанием '''
- Из большего числа вычитается меньшее
- Из большего числа вычитается меньшее
Строка 95:
Строка 112:
60 – 60 = 0
60 – 60 = 0
-
Конец: Наиболее общий делитель чисел 300 и 180 – 60.
+
''Конец: ''Наиболее общий делитель чисел 300 и 180 – 60.
<br>
<br>
-
[[Image:Alg-evkl.jpg]]
+
[[Image:Alg-evkl.jpg|480px|Алгоритм Евклида]]
<br>
<br>
Строка 111:
Строка 128:
<br>
<br>
-
При нахождении наибольшей общей меры двух отрезков поступают такими же способами, что и выше.
+
При нахождении наибольшей общей меры двух '''[[Точка, пряма, площина. Промінь. Відрізок. Презентація уроку|отрезков]]''' поступают такими же способами, что и выше.
-
Операция деления с остатком заменяется ее геометрическим аналогом: меньший отрезок откладывают на больший столько раз, сколько возможно, а оставшуюся часть большего отрезка (а это остаток деления) откладывают на меньшем отрезке.
+
Операция деления с остатком заменяется ее геометрическим аналогом: меньший '''[[Точка, пряма, площина. Промінь. Відрізок|отрезок]]''' откладывают на больший столько раз, сколько возможно, а оставшуюся часть большего отрезка (а это остаток деления) откладывают на меньшем отрезке.
Если отрезки ''a ''и''b'' соизмерыми, то последний не нулевой остаток даст наибольшую общую меру отрезков.
Если отрезки ''a ''и''b'' соизмерыми, то последний не нулевой остаток даст наибольшую общую меру отрезков.
Строка 121:
Строка 138:
<br>
<br>
-
'''Пример.'''
+
'''Пример:'''
В качестве отрезков возьмём сторону AB и AC равнобедренного треугольника ABC, у которого A=C = 72°, B= 36°.
В качестве отрезков возьмём сторону AB и AC равнобедренного треугольника ABC, у которого A=C = 72°, B= 36°.
Строка 131:
Строка 148:
<br>
<br>
-
{{#ev:youtube|19DWiE1bErA}}
+
=== Вопросы ===
+
+
''1. Что представляет собой алгоритм Евклида?''
+
+
''2. Что такое наибольший общий делитель?''
<br>
<br>
-
'''Вопросы:'''
+
== Список использованных источников ==
-
1. Что представляет собой алгоритм Евклида?
+
''1. Урок на тему: «Алгоритм Эвклида», Корчевой П. И., г. Луцк''
-
2. Что такое наибольший общий делитель?
+
''2. Щетников А. И. Алгоритм Евклида и непрерывные дроби. - Новосибирск: АНТ, 2003 г.''
-
<br>
+
''3. Коунтинхо С. Введение в теорию чисел. Алгоритм RSA, – М., 2001 г.''
-
''Список использованных источников: ''
+
''4. Кострикин А.И. Введение в алгебру, – М., 2000 г.''
-
1. Урок на тему: «Алгоритм Эвклида», Корчевой П. И., г. Луцк
+
----
-
2. Щетников А. И. Алгоритм Евклида и непрерывные дроби. - Новосибирск: АНТ, 2003 г.
+
''<br> Отредактировано и выслано преподавателем '''[http://xvatit.com/vuzi/ukraine-ukr/ Киевского национального университета им. Тараса Шевченко]''' Соловьевым М. С.''
-
3. Коунтинхо С. Введение в теорию чисел. Алгоритм RSA, – М., 2001 г.
+
----
-
4. Кострикин А.И. Введение в алгебру, – М., 2000 г.
-
''<br> Отредактировано и выслано преподавателем Киевского национального университета им. Тараса Шевченко Соловьевым М. С.''
-
<br> Если у вас есть исправления или предложения к данному уроку, [http://xvatit.com/index.php?do=feedback напишите нам].
+
'''Над уроком работали'''
+
+
Корчевой П. И.
+
+
Соловьев М. С.
+
+
<br>
+
+
----
+
+
<br>
-
Если вы хотите увидеть другие корректировки и пожелания к урокам, смотрите здесь - [http://xvatit.com/forum/ Образовательный форум].
+
Поставить вопрос о современном образовании, выразить идею или решить назревшую проблему Вы можете на [http://xvatit.com/forum/ '''Образовательном форуме'''], где на международном уровне собирается образовательный совет свежей мысли и действия. Создав [http://xvatit.com/club/blogs/ '''блог,'''] Вы не только повысите свой статус, как компетентного преподавателя, но и сделаете весомый вклад в развитие школы будущего. [http://xvatit.com/school/guild/ '''Гильдия Лидеров Образования'''] открывает двери для специалистов высшего ранга и приглашает к сотрудничеству в направлении создания лучших в мире школ.<br>
Научить находить наиболее общие делители разными математическими способами.
Ход урока
Понятие Алгоритм Евклида
Алгоритм Евклида является одним из древнейших математических формул, которой уже более 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 г.
Поставить вопрос о современном образовании, выразить идею или решить назревшую проблему Вы можете на Образовательном форуме, где на международном уровне собирается образовательный совет свежей мысли и действия. Создав блог, Вы не только повысите свой статус, как компетентного преподавателя, но и сделаете весомый вклад в развитие школы будущего. Гильдия Лидеров Образования открывает двери для специалистов высшего ранга и приглашает к сотрудничеству в направлении создания лучших в мире школ.
