Класс: 6
Цели урока:
- закрепить алгоритм нахождения наибольшего общего делителя с помощью разложения на множители;
- повторить сопутствующие определения и понятия;
- познакомить учащихся с алгоритмом Евклида;
- формировать навыки математической культуры
Оборудование: компьютер, проектор, экран.
Ход урока
1. Орг.момент (проверка готовности учащихся к уроку, отметка отсутствующих) (1 мин)
2. Устная работа: (6 мин)
1. Замените произведение степенью:
- Вычислите: 2 3 ; 5 2 ; 3 3 ; 10 4 .
- Найдите значение выражения: (3?3?5?11): (3?11). Какой вывод можно сделать?
- Выполните деление a на b , если а=170, b=35. Запишите равенством, чему равно а.
- Выясните и объясните, делится ли без остатка число а на число b, если:
г) а*а*а*а*а
Данное равенство записать в общем виде: а будет делимым, а b - делителем. Пусть частное равно q, а остаток r, тогда: а = bq + r , причем q может быть как натуральным числом, так и нулем. Любым ли числом может быть r? [ r - натуральное число, причем 0 < r < b .] Что можно сказать о числах а и b, если r = 0? Деление нацело - частный случай деления с остатком.
а) а = 2 3 * 3 * 5 * 7;
б) а = 2 4 * 3 * 5 7 ;
b = 2 7 * 3 * 5 4
в) а = 2 * 3 4 * 5 * 13;
b = 2 * 3 3 * 5 * 11.
3. Актуализация базовых знаний (10 мин)
1) Вопросы:
Что называют делителем числа а ?
Какое число называют простым?
Что значит разложить число на простые множители?
Сформулируйте признаки делимости на 2, 3, 5, 9,10;
Приведите пример однозначного составного числа;
Верно ли, что число 77-простое число?
Почему, если одно число можно разложить на 2 простых множителя, а другое на 3 простых множителя, то эти числа не равны?
Каким числом: простым или составным является произведение двух простых чисел?
Что называется наибольшим общим делителем двух или более чисел?
Какие числа называются взаимно-простыми?
Повторить способы нахождения НОД: Для поиска НОД натуральных чисел существуют различные алгоритмы
1 способ: Если даны два числа и они сравнительно невелики, то лучший алгоритм - непосредственный перебор. Однако для больших чисел находить НОД(а;b) путем перечисления всех делителей чисел а и b - процесс трудоемкий и ненадежный.
Полезно помнить, что НОД любого количества чисел не превосходит наименьшего из них.
2 способ: с помощью разложения чисел на множители (наиболее распространенный) (Приложение, слайд1)
2) Вычислите НОД чисел 24 и 16.
3) Разложите на простые множители числа: 875 и 8000 и вычислите НОД этих чисел.
(На примере числа 8000 повторить более простой способ разложения на простые множители чисел, оканчивающихся нулями: так как 10=2 *5, то 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6 * 5 3)
4) Может ли НОД трех чисел быть равен 15, если их произведение равно 3000? [ нет , так как
15 = 3 * 5, значит, число 3 должно входить в разложение каждого из трех чисел. Но, 3000 = 2 3 * 3 * 5 3 .]
5) Решите задачу "В класс привезли учебники: по математике 24, по истории 36 и по географии 48. Какое наибольшее число комплектов можно составить из этих книг так, чтобы в каждом было одинаковое число книг по математике, истории и географии? По сколько книг будет в каждом комплекте?"
4. Проверочная работа (Приложение, слайд 2) (6 мин)
5. Изучение нового материала (10 мин)
Учитель: изученный способ отыскания НОД(а, b) прост, понятен и удобен, но у него есть существенный недостаток: если данные числа велики, да еще не очень легко раскладываются на множители, то задача отыскания НОД(а, b) становится довольно трудной. К тому же может оказаться, что, основательно потрудившись, мы убедимся, что НОД(а, b)=1 и вроде вся работа проделана зря.
Евклид нашел замечательный способ отыскания НОД(а,b) без какой бы то ни было предварительной обработки чисел. (Приложение, слайды 3 и 4) Впоследствии этот алгоритм стали называть алгоритмом Евклида)
Познакомимся с алгоритмом Евклида. Пусть требуется найти НОД(102;84). Разделим одно число на другое и определим остаток.
Теперь проделаем такую же операцию для чисел 84 и 18:
Следующий шаг - для 18 и 12:
Теперь -для 12 и 6:
0-остаток. Процесс закончился.
Этот процесс не может быть бесконечным, потому что остатки убывают, оставаясь неотрицательными целыми числами, множество которых, как известно, ограничено снизу:
84 >18 > 12> 6 >0
Если присмотреться к записанным равенствам, то можно установить, что НОД всех пар чисел равны между собой (предложить учащимся подумать -почему?),
то есть НОД(102;84)=НОД(84;18)=НОД(18;12)=НОД(12;6)=6. Но число 6-последний, не равный 0 остаток.
Действительно, если с - произвольный общий делитель чисел а и b, то r = a - bq делится на c; и наоборот, если с - произвольный общий делитель чисел b и r, то а делится на с. То есть, все общие делители пар (а; b) и (b; r) совпадают, а значит, совпадают и их наибольшие общие делители.
Удобство алгоритма Евклида становится особенно заметным, если применить форму записи в виде таблицы:
В этой табличке сначала записывают исходные числа, делят в уме, записывая остатки справа, а частные -внизу, пока процесс не закончится. Последний делитель и есть НОД.
Таким образом, наибольшим общим делителем двух чисел является последний, не равный 0 остаток при делении большего числа на меньшее , то есть если a = b * q + r, то НОД(a; b) = НОД(b; r)
Такая последовательность операций и называется алгоритмом Евклида . Данный алгоритм позволяет находить НОД чисел, не разлагая их на множители (Приложение, слайд 5)
6. Упражнения(10 мин)
1. Целесообразно рассмотреть пример. Пусть надо найти НОД чисел 323 и 437. Сделать это подбором или разложением на простые множители не просто, так как ни одно из этих чисел не кратно 2, 3, 5, 7, 11. Поступаем следующим образом (
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 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) 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 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.
Посмотреть все слайды