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

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

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

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

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

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

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

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да 7 M N8 24, нет

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да 7 M N8 24, нет

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да 7 M N8 24, нет 8N=N-M

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да 7 M N8 24, нет 8N=N-M

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да 7 M N8 24, нет 8N=N-M816 9 M N8 16, да

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да 7 M N8 24, нет 8N=N-M816 9 M N8 16, да

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да 7 M N8 24, нет 8N=N-M816 9 M N8 16, да 10 M N8 16, нет

Трассировочная таблица алгоритма Евклида М=32, N=24 Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц шагоперацияMNусловие 1Ввод М32 2Ввод N M N32 24, да 4 M N32 24, да 5M=M-N824 6 M N8 24, да 7 M N8 24, нет 8N=N-M816 9 M N8 16, да 10 M N8 16, нет

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

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

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

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

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

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

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

Программа на Паскале 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. Н А Ч А Л О Ввод M и N M N N=N-MM=M-N M N нет да нет Вывод M К О Н Е Ц

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

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

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

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