Урок по теме "Алгоритм Евклида"
методическая разработка по информатике и икт (9 класс) на тему
Предварительный просмотр:
Урок информатики по теме: «Алгоритм Евклида»
Учитель: Тимофеева Светлана Алексеевна, ГБОУ СОШ № 233
Цели урока:
- Образовательные:
- научиться применять алгоритм Евклида для нахождения НОД двух и трех чисел;
- закрепить навыки по использованию алгоритмических структур «ветвление» и «цикл с предусловием»;
- получить опыт написания и отладки программ на языке программирования Паскаль.
- Воспитательная:
- воспитание самостоятельности и ответственности при изучении нового материала.
- Развивающая:
- развитие внимания и аналитического мышления.
Тип урока: комбинированный.
Технические средства: компьютеры, проектор, экран для проектора.
Программное обеспечение: операционная система Windows ХР, редактор презентаций Microsoft PowerPoint, система программирования Pascal ABC.
План урока:
I. Организационный момент.
Здравствуйте, ребята. Тема нашего сегодняшнего урока: «Алгоритм Евклида». Конечно, имя этого математика вам хорошо известно. Он внес важный вклад в развитие науки математики. А сегодня на уроке вы узнаете, как одно из сформулированных им правил используется в информатике.
II. Актуализация знаний.
Последние несколько уроков были посвящены основам программирования на языке Паскаль. Ответьте на вопросы:
Какие типы алгоритмических структур вы знаете?
Какая структура называется линейной?
Какая структура называется разветвляющейся?
Какая структура называется циклической?
III. Изучение нового материала.
Задача, которую мы с вами будем решать, известна вам из курса математики 6 класса. Нам нужно найти наибольший общий делитель (НОД) двух чисел М и N.
Что такое НОД двух натуральных чисел? (Это самое большое натуральное число, на которое они делятся нацело). (Слайд 2)
Давайте вспомним, как вы находили НОД на уроках математики в 6 классе? (Слайд 3)
Если этот алгоритм переводить на язык программирования, то придется решить следующие задачи (Слайд 4):
- Разложить числа на простые множители.
- Найти общие множители.
- Найти их произведение.
Каждая из этих задач по-своему сложная. Поэтому для составления программы мы будем использовать алгоритм, который был сформулирован в 3 веке до н.э. древнегреческим математиком Евклидом. Идея этого алгоритма основана на двух свойствах (Слайд 5):
1. Если M>N, то НОД (M, N) = НОД (M-N, N)
2. НОД (M, M) = M
Например: НОД (12, 18) = НОД (12, 18-12) = НОД (12, 6) = НОД (12-6, 6) = НОД (6, 6) = 6.
Иными словами, алгоритм Евклида для «ручного» счета выглядит так (Слайд 6):
- Если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма.
- Заменить большее число разностью большего и меньшего из чисел.
- Вернуться к выполнению п. 1.
Рассмотрим блок-схему для описания алгоритма Евклида (Слайд 7):
Какие алгоритмические структуры в ней присутствуют? (Цикл-пока с вложенным ветвлением). Как они работают? (Слайды 8-9)
Рассмотрим подробно трассировочную таблицу алгоритма для исходных значений M=32, N=24 (Слайды 10-34).
Теперь вернемся к блок-схеме алгоритма Евклида и попробуем написать на ее основе программу на языке Паскаль (Слайды 35-36)
Program Evklid;
var m, n: integer;
begin
writeln (’Введите m и n ’);
readln (m, n);
while m<>n do
begin
if m>n
then m:=m-n
else n:=n-m
end;
write (’НОД=’, m)
end.
IV. Практическая работа.
1. Выполнить на компьютере полученную программу. Протестировать ее на значениях:
1) M=32, N=24; 2) M=696, N=234.
2. Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:
M х N = НОД (M, N) х НОК (M, N).
V. Домашнее задание.
Составить программу нахождения наибольшего общего делителя трех чисел, используя формулу:
НОД (A, B, C) = НОД (НОД (A, B), C).
VI. Подведение итогов, выставление оценок.
По теме: методические разработки, презентации и конспекты
Алгоритм Евклида
Алгоритм Евклида- это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел....
Биография Евклида
Дополнительный материал к уроку.Биография Евклида...
![](/sites/default/files/pictures/2014/09/04/picture-105978-1409830556.jpg)
Конспект урока по ФГОС по теме:"Алгоритм Евклида" 9 класс
Урок разработан в соответсвии с ФГОС. Это самостоятельная учебная деятельность по карточкам. В карточке описание всех этапов построения модели....
Презентация к уроку геометрии в 7 классе " От Евклида до Лобачевского"
Презентация к уроку геометрии в 7 классе, история развития геометрии...
![](/sites/default/files/pictures/2011/12/03/picture-38981.jpg)
Открытый урок по теме "Алгоритм Евклида" 5 класс
Этот урок продолжает тему НОД и НОК в 5 классе. Обучающиеся знакомятся в алгоритмом Евклида как с еще одним способом нахождения НОД двух чисел....
![](/sites/default/files/pictures/2019/04/08/picture-1133559-1554750218.jpg)
Открытый урок "Оператор цикла с предусловием и алгоритм Евклида"
Конспект урока "Оператор цикла с предусловием и алгоритм Евклида" по дисциплине "Основы программирования"...
![](/sites/default/files/pictures/2021/10/17/picture-1033580-1634454715.jpg)
Презентация к уроку математики 10 по теме "Алгоритм Евклида"
презентацию можно использовать при объяснении нового материала...