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