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