Алгоритм Евклида

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

Цели урока:

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

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

   • закрепить навыки по использованию алгоритмических структур «Ветвление» и «Цикл»

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

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

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

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

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

План урока:

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

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

• Объяснение новой темы

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

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

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

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

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

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

Вопросы:

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

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

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

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

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

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

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

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

О Евклиде;

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

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

1. Свойство, что если MN, то НОД(М, 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 mn do

begin

if mn

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.Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

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

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