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

Тема: «Алгоритм Евклида» Цели урока: 1. Образовательные: o научиться применять алгоритм Евклида для нахождения НОД двух и трех чисел закрепить навыки по использованию алгоритмических структур «Ветвление» и o «Цикл» o получить опыт написания и отладки программ на языке программирования Паскаль 2. Воспитательная: o формирование самостоятельности и ответственности при изучении нового материала 3. Развивающая: o развитие внимания и аналитического мышления План урока:  Организационный момент  Актуализация знаний  Объяснение новой темы  Практическая часть  Подведение итогов урока  Домашнее задание. Организационный момент Приветствие. Кто отсутствует. Число. Тема урока. Вопросы по домашнему заданию. Актуализация знаний. Вопросы: Какие типы алгоритмических структур вы знаете? Какая структура называется линейной? (Бл-сх) Какая структура называется разветвляющейся? (Бл-сх) Какая структура называется циклической? (Бл-сх) Какие виды циклов вы знаете? Как реализуется на языке программирования Паскаль цикл с известным числом повторений? Как реализуется на языке программирования Паскаль цикл с неизвестным числом повторений? Объяснение новой темы (презентация) О Евклиде; Идея алгоритма Евклида Идея этого алгоритма основана на: 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 = 2. Проверить, являются ли два данных числа взаимно простыми. Примечание. Два числа 24; М = 696, N = 234. называются взаимно простыми, если их наибольший общий делитель равен 1. Подведение итогов урока Сегодня на уроке мы познакомились с алгоритмом Евклида, позволяющим находить НОД двух целых неотрицательных чисел, написали программу на языке программирования Паскаль, реализующую данный алгоритм. На дом вы получите задание, в котором вы будете применять данный алгоритм для нахождения НОД трех чисел и НОК двух чисел. Домашнее задание. 1.Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу: НОД(А, B, С) = НОД(НОД(А, В), С) 2.Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу: Выставление оценок. А  В = НОД(А, В)  НОК(А, В)