Презентация по информатике "Программирование цикла. Алгоритм Евклида."

Программирование цикла. Алгоритм Евклида. Цель урока: освоить программирование циклов с предусловием на примере Алгоритма Евклида. Мостовая Елена Евгеньевна, учитель информатики, ГБОУ СОШ № 1370, г. Москва

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программа на Паскале НАЧАЛО Ввод M и N MN нет да нет N=N-M MN да M=M-N Вывод M КОНЕЦ Program Evklid; var m,n:integer; Begin writeln(‘Введите m и n’); readln (m,n); while mn do begin If m>n then m:=m-n else n:=n-m end; write (‘НОД=‘,m); end.

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

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

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

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