Урок информатики в 9 классе по теме: «Алгоритм Евклида»

• 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 слайд

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

Урок информатики в 9 классе по теме: «Алгоритм Евклида»

Цели урока:

·        Образовательные:

o  научиться применять алгоритм Евклида для нахождения НОД двух и трех чисел;

o  закрепить навыки по использованию алгоритмических структур «ветвление» и «цикл с предусловием»;

o  получить опыт написания и отладки программ на языке программирования Паскаль.

·        Воспитательная:

o   воспитание самостоятельности и ответственности при изучении нового материала.

·        Развивающая:

o   развитие внимания и аналитического мышления.

Тип урока: комбинированный.

Технические средства: компьютеры, проектор, экран для проектора.

Программное обеспечение: операционная система Windows, редактор презентаций Microsoft PowerPoint, система программирования Turbo Pascal.

План урока:

I. Организационный момент.

Здравствуйте, ребята. Тема нашего сегодняшнего урока: «Алгоритм Евклида». Конечно, имя этого математика вам хорошо известно. Он внес важный вклад в развитие науки математики. А сегодня на уроке вы узнаете, как одно из сформулированных им правил используется в информатике.

II. Актуализация знаний.

Последние несколько уроков были посвящены основам программирования на языке Паскаль. Ответьте на вопросы:

-       Какие типы алгоритмических структур вы знаете?

-       Какая структура называется линейной? 

-       Какая структура называется разветвляющейся?

-       Какая структура называется циклической?

III. Изучение нового материала.

Задача, которую мы с вами будем решать, известна вам из курса математики 6 класса. Нам нужно найти наибольший общий делитель (НОД) двух чисел М и N.

Что такое НОД двух натуральных чисел? (Это самое большое натуральное число, на которое они делятся нацело). (Слайд 2)

Давайте вспомним, как вы находили НОД на уроках математики в 6 классе? (Слайд 3)

Если этот алгоритм переводить на язык программирования, то придется решить следующие задачи (Слайд 4):

1.     Разложить числа на простые множители.

2.     Найти общие множители.

3.     Найти их произведение.

Каждая из этих задач по-своему сложная. Поэтому для составления программы мы будем использовать алгоритм, который был сформулирован в 3 веке до н.э. древнегреческим математиком Евклидом. Идея этого алгоритма основана на двух свойствах (Слайд 5):

1. Если M>N, то НОД (M, N) = НОД (M-N, N)

2. НОД (M, M) = M

Например: НОД (12, 18) = НОД (12, 18-12) = НОД (12, 6) = НОД (12-6, 6) = НОД (6, 6) = 6.

Иными словами, алгоритм Евклида для «ручного» счета выглядит так   (Слайд 6):

1.     Если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма.

2.     Заменить большее число разностью большего и меньшего из чисел.

3.     Вернуться к выполнению п. 1.

Рассмотрим блок-схему для описания алгоритма Евклида (Слайд 7):

 

Какие алгоритмические структуры в ней присутствуют? (Цикл-пока с вложенным ветвлением). Как они работают? (Слайды 8-9)

Рассмотрим подробно трассировочную таблицу алгоритма для исходных значений M=32, N=24 (Слайды 10-34).

Теперь вернемся к блок-схеме алгоритма Евклида и попробуем написать на ее основе программу на языке Паскаль (Слайды 35-36)

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.

IV. Практическая работа.

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

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

V. Домашнее задание.

Составить программу нахождения наибольшего общего делителя трех чисел, используя формулу:

 НОД (A, B, C) = НОД (НОД (A, B), C).

VI. Подведение итогов, выставление оценок.