Презентация на тему: Алгоритм Евклида

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

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

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

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

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

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

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

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

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

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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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

Трассировочная таблица алгоритма Евклида М=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, 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 конец

Блок-схема алгоритма Евклида Н А Ч А Л О Ввод M и N M N N=N-M M=M-N 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 M N N=N-M M=M-N M N нет да да нет К О Н Е Ц P=M*N HOK=P/M Вывод НОК

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