Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
Подписи к слайдам:
АЛГОРИТМ ЕВКЛИДА ЕВКЛИД, древнегреческий математик. Работал в Александрии в 3 в. до н. э. Главный труд "Начала" (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки. Евклид (365-300 до. н. э.)
АЛГОРИТМ ЕВКЛИДА Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. Евклид (365-300 до. н. э.) Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις - «взаимное вычитание».
Вычисление НОД НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. НОД(a , b)= НОД(a-b, b)= НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (18 , 45) = НОД (18 , 45-18) = НОД (18 , 27) = НОД (18 , 9) = =НОД(9,9)=9 Пример:
ШАГ Операция M N Условие 1 Ввод M 48 2 Ввод N 18 3 M N 48 18, да 4 M>N 48>18, да 5 M:=M-N 30 6 M N 30 18, да 7 M>N 30 >18, да 8 M:=M-N 12 9 M N 12 18, да 10 M>N 12 >18, нет 11 N:=N-M 6 12 M N 12 6, да 13 M>N 12 >6, да 14 M:=M-N 6 15 M N 6 6, нет 16 Вывод M
program Evklid ; var m, n: integer; begin writeln (" vved 2 chisla "); readln (m,n); while mn do begin if m>n then m:=m-n else n:= n-m ; end; write ("nod=",m); readln end.
0.Выполните на компьютере программу Evklid . Протестируйте её при значениях М=32, N=24; M=696, N=234. 1 . Проверить, являются ли два данных числа взаимно простыми. Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1. 2 . Найти наименьшее общее кратное (НОК) чисел n и m , если НОК(n , m) = n * m / НОД (n , m). 3 . Даны натуральные числа m и n . Найти такие натуральные p и q , не имеющие общих делителей, что p / q = m / n . 4. Найти НОД трех чисел. Примечание. НОД(a , b , c)= НОД(НОД(a , b), c) Задачи
Предварительный просмотр:
Тема: «Алгоритм Евклида»
Цели урока:
- Образовательные:
- научиться применять алгоритм Евклида для нахождения НОД двух и трех чисел
- закрепить навыки по использованию алгоритмических структур «Ветвление» и «Цикл»
- получить опыт написания и отладки программ на языке программирования Паскаль
- Воспитательная:
- формирование самостоятельности и ответственности при изучении нового материала
- Развивающая:
- развитие внимания и аналитического мышления
План урока:
- Организационный момент
- Актуализация знаний
- Объяснение новой темы
- Практическая часть
- Подведение итогов урока
- Домашнее задание.
Организационный момент
Приветствие. Кто отсутствует. Число. Тема урока. Вопросы по домашнему заданию.
Актуализация знаний.
Вопросы:
Какие типы алгоритмических структур вы знаете?
Какая структура называется линейной? (Бл-сх)
Какая структура называется разветвляющейся? (Бл-сх)
Какая структура называется циклической? (Бл-сх)
Какие виды циклов вы знаете?
Как реализуется на языке программирования Паскаль цикл с известным числом повторений?
Как реализуется на языке программирования Паскаль цикл с неизвестным числом повторений?
Объяснение новой темы (презентация)
О Евклиде;
Идея алгоритма Евклида
Идея этого алгоритма основана на:
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 mn do
Begin
If m>n
Then m:=m-n
Else n:=n-m;
End;
Write ("nod=",m);
readln
end.
Практическая часть
Вопросы и задания:
- Выполните на компьютере программу Evklid. Протестируйте ее на значениях М= 32, N = 24; М = 696, N = 234.
- Проверить, являются ли два данных числа взаимно простыми. Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.
Подведение итогов урока
Сегодня на уроке мы познакомились с алгоритмом Евклида, позволяющим находить НОД двух целых неотрицательных чисел, написали программу на языке программирования Паскаль, реализующую данный алгоритм. На дом вы получите задание, в котором вы будете применять данный алгоритм для нахождения НОД трех чисел и НОК двух чисел.
Домашнее задание.
1. Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:
НОД(А, B, С) = НОД(НОД(А, В), С)
2.Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:
А В = НОД(А, В) НОК(А, В)
Слайд 2
Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. Евклид (365-300 до. н. э.) Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις - «взаимное вычитание».
Слайд 3
Вычисление НОД
НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. НОД(a,b)= НОД(a-b, b)= НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (18, 45)= НОД (18, 45-18)= НОД (18, 27)=НОД (18, 9)= =НОД(9,9)=9 Пример:
Слайд 4
Слайд 5
program Evklid; var m, n: integer; begin writeln ("vved 2 chisla"); readln (m,n); while mn do begin if m>n then m:=m-n else n:=n-m; end; write ("nod=",m); readln end.
Слайд 6
0.Выполните на компьютере программу Evklid. Протестируйте её при значениях М=32, N=24; M=696, N=234. 1. Проверить, являются ли два данных числа взаимно простыми. Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1. 2.Найти наименьшее общее кратное (НОК) чисел n и m, если НОК(n, m) = n * m / НОД (n, m). 3.Даны натуральные числа m и n. Найти такие натуральные p и q, не имеющие общих делителей, что p / q = m / n. 4. Найти НОД трех чисел. Примечание. НОД(a, b, c)= НОД(НОД(a, b), c) Задачи
Слайд 7
ЕВКЛИД, древнегреческий математик. Работал в Александрии в 3 в. до н. э. Главный труд "Начала" (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.
Посмотреть все слайды
Постановка Задачи Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел. Вспомним математику. Наибольший общий делитель двух натуральных чисел это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так: НОД(12,18) = 6. Обозначим исходные данные как М и N. Постановка задачи выглядит следующим образом: Дано: М, N Найти: НОД(М,N).
N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа." title="Идея алгоритма Идея этого алгоритма основана на том свойстве, что если M>N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа." class="link_thumb"> 4 Идея алгоритма Идея этого алгоритма основана на том свойстве, что если M>N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа. N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа."> N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа."> N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа." title="Идея алгоритма Идея этого алгоритма основана на том свойстве, что если M>N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа."> title="Идея алгоритма Идея этого алгоритма основана на том свойстве, что если M>N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа.">
N). Это значит, что М = тК, N = пК, где т, п натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К делитель числа М - N. Значит, все общие делители чисел М и N являются делителями" title="Доказательство Пусть К общий делитель М и. N (M>N). Это значит, что М = тК, N = пК, где т, п натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К делитель числа М - N. Значит, все общие делители чисел М и N являются делителями" class="link_thumb"> 5 Доказательство Пусть К общий делитель М и. N (M>N). Это значит, что М = тК, N = пК, где т, п натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их раз ности M-N, в том числе и наибольший общий делитель. Отсюда: НОД(М,N) = НОД(М - N,N). Второе очевидное свойство: НОД(М,М) = М. N). Это значит, что М = тК, N = пК, где т, п натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К делитель числа М - N. Значит, все общие делители чисел М и N являются делителями"> N). Это значит, что М = тК, N = пК, где т, п натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их раз ности M-N, в том числе и наибольший общий делитель. Отсюда: НОД(М,N) = НОД(М - N,N). Второе очевидное свойство: НОД(М,М) = М."> N). Это значит, что М = тК, N = пК, где т, п натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К делитель числа М - N. Значит, все общие делители чисел М и N являются делителями" title="Доказательство Пусть К общий делитель М и. N (M>N). Это значит, что М = тК, N = пК, где т, п натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К делитель числа М - N. Значит, все общие делители чисел М и N являются делителями"> title="Доказательство Пусть К общий делитель М и. N (M>N). Это значит, что М = тК, N = пК, где т, п натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К делитель числа М - N. Значит, все общие делители чисел М и N являются делителями">
Программа на языке Паскаль Program Evklid; var М, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end.
N then M:=M-N else N:=N-M end; write("HOD=",M) end.">
N then M:=M-N else N:=N-M end; write("HOD=",M) end.">
N then M:=M-N else N:=N-M end; write("HOD=",M) end." title="Программа на языке Паскаль Program Evklid; var М, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end.">
N then M:=M-N else N:=N-M end; write("HOD=",M) end." title="Программа на языке Паскаль Program Evklid; var М, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end.">
Cлайд 1
Cлайд 2
АЛГОРИТМ ЕВКЛИДА Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. Евклид (365-300 до. н. э.) Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις - «взаимное вычитание».Cлайд 3
Вычисление НОД НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. НОД(a, b)= НОД(a-b, b)= НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27)= НОД (18, 9) = =НОД(9,9)=9 Пример:Cлайд 4
ШАГ Операция M N Условие 1 ВводM 48 2 ВводN 18 3 M N 48 18,да 4 M>N 48>18,да 5 M:=M-N 30 6 M N 30 18, да 7 M>N 30>18,да 8 M:=M-N 12 9 M N 12 18,да 10 M>N 12>18,нет 11 N:=N-M 6 12 M N 12 6,да 13 M>N 12>6,да 14 M:=M-N 6 15 M N 6 6, нет 16 ВыводMCлайд 5
program Evklid; var m, n: integer; begin writeln ("vved 2 chisla"); readln (m,n); while mn do begin if m>n then m:=m-n else n:=n-m; end; write ("nod=",m); readln end.Cлайд 6
0.Выполните на компьютере программу Evklid. Протестируйте её при значениях М=32, N=24; M=696, N=234. 1. Проверить, являются ли два данных числа взаимно простыми. Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1. 2. Найти наименьшее общее кратное (НОК) чисел n и m, если НОК(n, m) = n * m / НОД (n, m). 3. Даны натуральные числа m и n. Найти такие натуральные p и q, не имеющие общих делителей, что p / q = m / n. 4. Найти НОД трех чисел. Примечание. НОД(a, b, c)= НОД(НОД(a, b), c) ЗадачиCлайд 7
ЕВКЛИД, древнегреческий математик. Работал в Александрии в 3 в. до н. э. Главный труд "Начала" (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.