Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Конспекты / Урок информатики в 9 классе по теме: «Алгоритм Евклида»

Урок информатики в 9 классе по теме: «Алгоритм Евклида»


  • Информатика

Название документа Алгоритм Евклида.ppt

Поделитесь материалом с коллегами:

Программирование цикла. Алгоритм Евклида. Цель урока: освоить программировани...
Алгоритм Евклида ЕВКЛИД, древнегреческий математик. Работал в Александрии в 3...
Постановка задачи: Требуется составить программу определения наибольшего обще...
Постановка задачи: Дано: M и N Найти: НОД(M,N) НОД АЛГОРИТМ ЕВКЛИДА: Если два...
Блок-схема алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N н...
Структура алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N не...
Структура алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N не...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие...
Блок-схема алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N н...
Программа на Паскале Program Evklid; var m,n:integer; Begin writeln(‘Введите...
Отладка и тестирование задачи на ПК: Выполнить на ПК программу. Протестироват...
Постановка задачи: Составить программу нахождения наименьшего общего кратного...
Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N нет да да нет К О Н Е Ц P=M*N...
Источники материала: «Информатика и ИКТ- 9» учебник И.Г.Семакин. Л.А. Залогов...
1 из 38

Описание презентации по отдельным слайдам:

№ слайда 1 Программирование цикла. Алгоритм Евклида. Цель урока: освоить программировани
Описание слайда:

Программирование цикла. Алгоритм Евклида. Цель урока: освоить программирование циклов с предусловием на примере Алгоритма Евклида.

№ слайда 2 Алгоритм Евклида ЕВКЛИД, древнегреческий математик. Работал в Александрии в 3
Описание слайда:

Алгоритм Евклида ЕВКЛИД, древнегреческий математик. Работал в Александрии в 3 в. до н. э. Главный труд «Начала» (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов, оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.

№ слайда 3 Постановка задачи: Требуется составить программу определения наибольшего обще
Описание слайда:

Постановка задачи: Требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел НОД НОД двух натуральных чисел- это самое большое натуральное число, на которое они делятся нацело. НАПРИМЕР: НОД(12,18)=6

№ слайда 4 Постановка задачи: Дано: M и N Найти: НОД(M,N) НОД АЛГОРИТМ ЕВКЛИДА: Если два
Описание слайда:

Постановка задачи: Дано: M и N Найти: НОД(M,N) НОД АЛГОРИТМ ЕВКЛИДА: Если два числа равны, то ответ любое из них иначе перейти к 2) 2) Заменить большее число разностью большего и меньшего из чисел 3) Вернуться к 1)

№ слайда 5 Блок-схема алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N н
Описание слайда:

Блок-схема алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N нет да да нет Вывод M К О Н Е Ц

№ слайда 6 Структура алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N не
Описание слайда:

Структура алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N нет да да нет Вывод M К О Н Е Ц Цикл-пока Повторяет выполнение, пока значения M и N не равны друг другу

№ слайда 7 Структура алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N не
Описание слайда:

Структура алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N нет да да нет Вывод M К О Н Е Ц Вложенное ветвление Заменяет большее из двух значений на их разность

№ слайда 8 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 2 3 4 5 6 7 8 9 10 11 12 13 14

№ слайда 9 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 4 5 6 7 8 9 10 11 12 13 14

№ слайда 10 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 4 5 6 7 8 9 10 11 12 13 14

№ слайда 11 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 5 6 7 8 9 10 11 12 13 14

№ слайда 12 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 5 6 7 8 9 10 11 12 13 14

№ слайда 13 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 6 7 8 9 10 11 12 13 14

№ слайда 14 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 6 7 8 9 10 11 12 13 14

№ слайда 15 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 7 8 9 10 11 12 13 14

№ слайда 16 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 7 8 9 10 11 12 13 14

№ слайда 17 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 8 9 10 11 12 13 14

№ слайда 18 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 8 9 10 11 12 13 14

№ слайда 19 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 9 10 11 12 13 14

№ слайда 20 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 9 10 11 12 13 14

№ слайда 21 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 10 11 12 13 14

№ слайда 22 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 10 11 12 13 14

№ слайда 23 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 11 12 13 14

№ слайда 24 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 11 12 13 14

№ слайда 25 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 M  N 8  16, нет 11 12 13 14

№ слайда 26 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 M  N 8  16, нет 11 12 13 14

№ слайда 27 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 M  N 8  16, нет 11 N=N-M 8 8 12 13 14

№ слайда 28 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 M  N 8  16, нет 11 N=N-M 8 8 12 13 14

№ слайда 29 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 M  N 8  16, нет 11 N=N-M 8 8 12 M  N 88 нет 13 14

№ слайда 30 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 M  N 8  16, нет 11 N=N-M 8 8 12 M  N 88 нет 13 14

№ слайда 31 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 M  N 8  16, нет 11 N=N-M 8 8 12 M  N 88 нет 13 Вывод М 8 14

№ слайда 32 Трассировочная таблица алгоритма Евклида М=32, N=24 шаг	операция	M	N	условие
Описание слайда:

Трассировочная таблица алгоритма Евклида М=32, N=24 шаг операция M N условие 1 Ввод М 32 2 Ввод N 32 24 3 M  N 3224, да 4 M  N 32  24, да 5 M=M-N 8 24 6 M  N 824, да 7 M  N 8  24, нет 8 N=N-M 8 16 9 M  N 816, да 10 M  N 8  16, нет 11 N=N-M 8 8 12 M  N 88 нет 13 Вывод М 8 14 конец

№ слайда 33 Блок-схема алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N н
Описание слайда:

Блок-схема алгоритма Евклида Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N нет да да нет Вывод M К О Н Е Ц

№ слайда 34 Программа на Паскале Program Evklid; var m,n:integer; Begin writeln(‘Введите
Описание слайда:

Программа на Паскале 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.

№ слайда 35 Отладка и тестирование задачи на ПК: Выполнить на ПК программу. Протестироват
Описание слайда:

Отладка и тестирование задачи на ПК: Выполнить на ПК программу. Протестировать ее на значениях 1) M= 32 N=24 2) M= 696 N=234

№ слайда 36 Постановка задачи: Составить программу нахождения наименьшего общего кратного
Описание слайда:

Постановка задачи: Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу: А х В=НОД(А,В) х НОК (А,В)

№ слайда 37 Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N нет да да нет К О Н Е Ц P=M*N
Описание слайда:

Н А Ч А Л О Ввод M и N M  N N=N-M M=M-N M  N нет да да нет К О Н Е Ц P=M*N HOK=P/M Вывод НОК

№ слайда 38 Источники материала: «Информатика и ИКТ- 9» учебник И.Г.Семакин. Л.А. Залогов
Описание слайда:

Источники материала: «Информатика и ИКТ- 9» учебник И.Г.Семакин. Л.А. Залогова. С.В. Русаков. Л.В. Шестакова, М: Бином, 2012 г.

Название документа Конспект урока.doc

Поделитесь материалом с коллегами:

Урок информатики в 9 классе по теме: «Алгоритм Евклида»


Цели урока:

  • Образовательные:

  • научиться применять алгоритм Евклида для нахождения НОД двух и трех чисел;

  • закрепить навыки по использованию алгоритмических структур «ветвление» и «цикл с предусловием»;

  • получить опыт написания и отладки программ на языке программирования Паскаль.

  • Воспитательная:

  • воспитание самостоятельности и ответственности при изучении нового материала.

  • Развивающая:

  • развитие внимания и аналитического мышления.

Тип урока: комбинированный.

Технические средства: компьютеры, проектор, экран для проектора.

Программное обеспечение: операционная система Windows, редактор презентаций Microsoft PowerPoint, система программирования Turbo Pascal.

План урока:

I. Организационный момент.

Здравствуйте, ребята. Тема нашего сегодняшнего урока: «Алгоритм Евклида». Конечно, имя этого математика вам хорошо известно. Он внес важный вклад в развитие науки математики. А сегодня на уроке вы узнаете, как одно из сформулированных им правил используется в информатике.

II. Актуализация знаний.

Последние несколько уроков были посвящены основам программирования на языке Паскаль. Ответьте на вопросы:

  • Какие типы алгоритмических структур вы знаете?

  • Какая структура называется линейной?

  • Какая структура называется разветвляющейся?

  • Какая структура называется циклической?

III. Изучение нового материала.

Задача, которую мы с вами будем решать, известна вам из курса математики 6 класса. Нам нужно найти наибольший общий делитель (НОД) двух чисел М и N.

Что такое НОД двух натуральных чисел? (Это самое большое натуральное число, на которое они делятся нацело). (Слайд 2)

Давайте вспомним, как вы находили НОД на уроках математики в 6 классе? (Слайд 3)

Если этот алгоритм переводить на язык программирования, то придется решить следующие задачи (Слайд 4):

  1. Разложить числа на простые множители.

  2. Найти общие множители.

  3. Найти их произведение.

Каждая из этих задач по-своему сложная. Поэтому для составления программы мы будем использовать алгоритм, который был сформулирован в 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. Если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма.

  2. Заменить большее число разностью большего и меньшего из чисел.

  3. Вернуться к выполнению п. 1.

Рассмотрим блок-схему для описания алгоритма Евклида (Слайд 7):

hello_html_m66af4d4e.png















Какие алгоритмические структуры в ней присутствуют? (Цикл-пока с вложенным ветвлением). Как они работают? (Слайды 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. Подведение итогов, выставление оценок.


Автор
Дата добавления 03.10.2016
Раздел Информатика
Подраздел Конспекты
Просмотров207
Номер материала ДБ-234799
Получить свидетельство о публикации

Похожие материалы

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