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