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

• 1 слайд

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

• 2 слайд

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

• 3 слайд

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

• 4 слайд

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

• 5 слайд

  Блок-схема алгоритма Евклида
  Н А Ч А Л О
  Ввод 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
  К О Н Е Ц
  Цикл-пока
  Повторяет выполнение, пока значения M и N не равны друг другу
  

• 7 слайд

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

• 8 слайд

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

• 9 слайд

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

• 10 слайд

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

• 11 слайд

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

• 12 слайд

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

• 13 слайд

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

• 14 слайд

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

• 15 слайд

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

• 16 слайд

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

• 17 слайд

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

• 18 слайд

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

• 19 слайд

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

• 20 слайд

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

• 21 слайд

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

• 22 слайд

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

• 23 слайд

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

• 24 слайд

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

• 25 слайд

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

• 26 слайд

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

• 27 слайд

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

• 28 слайд

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

• 29 слайд

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

• 30 слайд

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

• 31 слайд

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

• 32 слайд

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

• 33 слайд

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

• 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
  HOK=P/M
  Вывод НОК
  

• 38 слайд

  Домашнее задание:
  §16 стр.101
  Составить программу нахождения наибольшего общего делителя трех чисел, используя формулу:
  НОД (A, B, C) = НОД (НОД (A, B), C).