Тема: Алгоритм Евклида для нахождения НОД.
Цели: повторить изученные ранее темы Наибольший общий делитель и наименьшее общее кратное, познакомить с алгоритмом Евклида.
Задачи обучения – повторить понятия Наибольший общий делитель и наименьшее общее кратное, правило их нахождения. Познакомить с алгоритмом Евклида. Закрепить алгоритм Евклида решением соответствующих заданий.
Задачи развития – развитие логического мышления, внимания, памяти речи, умения самостоятельно открывать новые знания, математической любознательности, познавательного интереса к предмету.
Задачи воспитания – воспитывать культуру математического мышления, взаимопомощь, выполнять самопроверку и анализировать свои ошибки.
Работа на карточках
Найдите НОД или НОК чисел и расшифруйте фразу:
3416
300
6
1
12
2
34
11
17
Д: НОД(33,88)
Г: НОК(9,40)
О: НОК(14,42)
Е: НОД(48,18)
Р: НОК(17,5)
С: НОД(48,24)
К: НОД (72,12)
Л: НОД(20,14)
Е: НОД(30,18)
М: НОК(25,12)
Т: НОК(4,8,16)
Н: НОК(12,40)
В: НОД(18,35)
А: НОД(17,34)
И: НОД(102,68)
Е: НОД(18,12)
В последнюю таблицу запишите оставшиеся пары чисел
Ответы:
3416
300
6
1
12
2
34
11
17
А
Л
Г
О
Р
И
Т
М
Е
В
К
Л
И
Д
А
Д: НОД(33,88)=11
Г: НОК(9,40)=360
О: НОК(14,42)=42
Е: НОД(48,18)=6
Р: НОК(17,5)=85
С: НОД(48,24)=24
К: НОД (72,12)=12
Л: НОД(20,14)=2
Е: НОД(30,18)=6
М: НОК(25,12)=300
Т: НОК(4,8,16)=16
Н: НОК(12,40)=120
В: НОД(18,35)=1
А: НОД(17,34)=17
И: НОД(102,68)=34
Е: НОД(18,12)=6
Отгадать ещё 2 слова
Что можно сказать о числах последней таблицы? Они взаимно простые, т.е. если мы разложим данные числа на простые множители, то у них не будет одинаковых множителей. Как найти НОД таких чисел? Нод таких чисел =1. А как найти НОК, что бы найти НОК нужно эти числа перемножить друг на друга.
В первой колонке пары чисел, в которые одно из них не делится на другое нацело. Т.е. остаток не равен 0.
Как вы находили НОД и НОК таких чисел. (С помощью разложения этих чисел на простые множители)
НОК(12,40)=2 3 *3*5=120
Вспомним правило нахождения НОД и НОК, найдем и проверим формулу НОК(а,в)=(а*b ):НОД(а,b )
3 *3*11=264
НОК(а,в)=(а*b ):НОД(а,b )
264=(33*88):11=3*88=264
НОК(20,14)=2 2 *5*7=140
НОК(а,в)=(а*b ):НОД(а,b )
140=(20*14):2=10*14=140
НОД(12,40)=2 2 =4
НОК(а,в)=(а*b ):НОД(а,b )
120=(12*40):4=3*4=120
Изучение новой темы:
НОД каких пар чисел получился 6?
6=НОД(48,18)=НОД(30,18)=НОД(12,18)
Что вы заметили? Как получили 30? 48-18
Как получили 12? 30-18
При а>в = НОД (а-в,в)
Т.е. НОД(а,в) При в>а = НОД(а,в-а)
Кто может продолжить это равенство?
6=НОД(48,18)=НОД(30,18)=НОД(12,18) = НОД(12,6)=НОД(6,6)=6
На этом правиле и основан алгоритм Евклида.
Алгори́тм Евкли́да - эффективный для нахождения двух . Алгоритм назван в честь , который впервые описал его в VII и X книгах « ».
В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.
Древнегреческие математики называли этот алгоритм- «взаимное вычитание».
Суть этого метода заключается в следующем: вычитай из большего числа меньшее пока числа не сравняются, заменяя большее разностью. Как только это произойдет НОД найден. (Пример на доске – числа 48 и 18)
Первый вопрос – равны ли эти числа? Нет не равны, следовательно мы из большего вычитаем меньшее 48-18 = 30. 30 не равно 18, значит 30-18= 12, 18-12=6, 12-6=6. То есть мы выполняем эти действия до тех пор пока числа не сравняются. Следовательно НОД(48,18)=6
Зная НОД чисел 48 и 18 найдите НОК. НОК(48,18)=(48*18):6=48*3=144
Найдем с помощью алгоритма Евклида НОД(102;68).
Найдем НОД (357;273)
Здесь мы 3 раза вычитали число 84 и три раза число 21.
Как, не производя вычитаний, узнать, сколько вычитаний будет в одной серии, и какая разность получится в итоге? Какие случаи нужно рассмотреть? (Указание : вспомните про деление.)
Общее правило можно сформулировать так: если число a не делится на b , то оно заменяется своим остатком от деления на b (в случае a < b этот остаток равен a ); если a делится на b , то заменяем его числом b . Точно такое же правило, с перестановкой a и b , действует и для b . Большее число делят на меньшее, затем меньшее на первый остаток, затем первый остаток – на второй остаток и т.д., пока не получится 0. Тогда последний остаток не равный 0 – это НОД .
Найти НОД (357;273).
357 273 273 84 84 21 НОД (357;273) = 21
273 1 252 3 21 4
84 21 0
357=1*273+84 273=3*84+21 84=4*21
НОД(357,273)=НОД(273,84)=НОД(84,21)=21
Удобство алгоритма Евклида становится особенно заметным, если применить форму записи в виде таблицы:
В этой табличке сначала записывают исходные числа, делят в уме, записывая остатки справа, а частные -внизу, пока процесс не закончится. Последний делитель и есть НОД.
Таким образом, наибольшим общим делителем двух чисел является последний, не равный 0 остаток при делении большего числа на меньшее , то есть если a = b * q + r, то НОД(a; b) = НОД(b; r)
Такая последовательность операций и называется алгоритмом Евклида .
1) С помощью алгоритма Евклида найти НОД чисел:
А) 703, 481, Б) 2112 и 1680; В) 5075 и 1450
НОД(703;481)=37
НОД(2112;1680)=48
НОД(5075;1450)=
Проверить полученные результаты на компьютере.
Задание детям на компьютере найти НОД и НОК для трех чисел с помощью программы нахождения НОД и НОК.
НОД (150, ____) = ____
НОД(450,315,135)=____
НОД (135, ____) = ____
НОД(2160,1350,1080)=____
НОД (1080, ____) = ____
НОД(5300,3180,2120)=____
НОД (2120, ____) = ____
(Чтобы найти НОД трех и более чисел, находят сначала НОД каких-нибудь двух из них, затем НОД найденного делителя и третьего данного числа.
и третьего данного числа.
7. Проверка полученных результатов на компьютере. Самостоятельное решение задач.
1) Для учащихся класса приготовили одинаковые подарки. Во всех подарках было 120 шоколадок, 280 конфет, и 320 орехов. Сколько учащихся в первом классе, если известно, что их больше 30?
Ответ:________________________
2) На станции стоят три пассажирских поезда: в первом – 418 мест в купейных вагонах, во втором – 494, а в третьем – 456. Сколько купейных вагонов в каждом поезде, если в каждом вагоне одинаковое число мест и их общее число больше 20? Ответ _________________________
3) Из 156 чайных, 234 белых и 390 красных роз сделали букеты, причем во всех букетах роз каждого вида было поровну и число таких букетов было больше 50. Сколько букетов сделали из этих роз и сколько роз каждого вида было в одном букете? Ответ_________________
Итог урока. С каким способом нахождения НОД и НОК мы познакомились на уроке. Алгоритм Евклида. Как по другому называют этот способ? (метод вычитания). В чем усовершенствовали этот способ? С помощью деления, большее число делят на меньшее, затем меньшее на первый остаток, затем первый остаток на второй остаток и т.д., до тех пор пока не получат 0. Последний отличный от нуля остаток и есть НОД чисел.
Слайд 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.">
