Алгоритм Евклида
презентация к уроку информатики и икт (9 класс) на тему

Тема: «Алгоритм Евклида»

Цели урока:

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

1. научиться применять алгоритм Евклида для нахождения НОД двух и трех чисел
2. закрепить навыки по использованию алгоритмических структур «Ветвление» и «Цикл»
3. получить опыт написания и отладки программ на языке программирования Паскаль

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

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

3. Развивающая:

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

План урока: 

1. Организационный момент
2. Актуализация знаний
3. Объяснение новой темы
4. Практическая часть
5. Подведение итогов урока
6. Домашнее задание.

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

Приветствие. Кто отсутствует. Число. Тема урока. Вопросы по домашнему заданию.

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

Вопросы:

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

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

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

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

Какие виды циклов вы знаете?

Как реализуется на языке программирования Паскаль цикл с известным числом повторений?

Как реализуется на языке программирования Паскаль цикл с неизвестным числом повторений?

Объяснение новой темы  (презентация)

О Евклиде;

Идея алгоритма Евклида

Идея этого алгоритма основана на:

1. Свойство, что если   M>N,   то  НОД(М, N) = НОД(М - N, N).

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

Доказательство: пусть К - общий делитель М и N (M> N). Это значит, что М = mК, N = nК, где m, n - натуральные числа, причем m > n. Тогда М - N = К(m - n), откуда следует, что К - делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N, в том числе и наибольший общий делитель.

2.Второе очевидное свойство:

НОД(М, М) = М.

Для "ручного" счета алгоритм Евклида выглядит так:

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

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

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

Блок-схема алгоритма Евклида

Программа на ЯП Паскаль

program Evklid;

var m, n: integer;

begin

writeln ('vved 2 chisla');

readln (m,n);

            while m<>n do

            begin

                   if m>n

                   then m:=m-n

                   else n:=n-m;

             end;

            write ('nod=',m);

readln

end.

Практическая часть

Вопросы и задания:

1. Выполните на компьютере программу Evklid. Протестируйте ее на значениях М= 32, N = 24; М = 696, N = 234.
2. Проверить, являются ли два данных числа взаимно простыми. Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.

Подведение итогов урока

Сегодня на уроке мы познакомились с алгоритмом Евклида, позволяющим находить НОД двух целых неотрицательных чисел, написали программу на языке программирования Паскаль, реализующую данный алгоритм. На дом вы получите задание, в котором вы будете применять данный алгоритм для нахождения НОД трех чисел и НОК двух чисел.

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

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

НОД(А, B, С) = НОД(НОД(А, В), С)

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

А  В = НОД(А, В)  НОК(А, В)

Выставление оценок.