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

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

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

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

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

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

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

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

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

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

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

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

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

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

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, да

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

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-N

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

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

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

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

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

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

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

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-M816 9 M N8 16, да

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

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

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

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

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

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

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

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

34 Программа на Паскале 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 К О Н Е Ц

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

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

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

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