Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) 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. Образовательные:

1. научиться применять алгоритм Евклида для нахождения НОД двух и трех чисел
2. закрепить навыки по использованию алгоритмических структур «Ветвление» и «Цикл»
3. получить опыт написания и отладки программ на языке программирования Паскаль

1. Воспитательная:

1. формирование самостоятельности и ответственности при изучении нового материала

1. Развивающая:

1. развитие внимания и аналитического мышления

План урока:

1. Организационный момент
2. Актуализация знаний
3. Объяснение новой темы
4. Практическая часть
5. Подведение итогов урока
6. Домашнее задание.

Организационный момент

Приветствие. Кто отсутствует. Число. Тема урока. Вопросы по домашнему заданию.

Актуализация знаний.

Вопросы:

Какие типы алгоритмических структур вы знаете?

Какая структура называется линейной? (Бл-сх)

Какая структура называется разветвляющейся? (Бл-сх)

Какая структура называется циклической? (Бл-сх)

Какие виды циклов вы знаете?

Как реализуется на языке программирования Паскаль цикл с известным числом повторений?

Как реализуется на языке программирования Паскаль цикл с неизвестным числом повторений?

Объяснение новой темы (презентация)

О Евклиде;

Идея алгоритма Евклида

Идея этого алгоритма основана на:

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.

Практическая часть

Вопросы и задания:

1. Выполните на компьютере программу Evklid. Протестируйте ее на значениях М= 32, N = 24; М = 696, N = 234.
2. Проверить, являются ли два данных числа взаимно простыми. Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.

Подведение итогов урока

Сегодня на уроке мы познакомились с алгоритмом Евклида, позволяющим находить НОД двух целых неотрицательных чисел, написали программу на языке программирования Паскаль, реализующую данный алгоритм. На дом вы получите задание, в котором вы будете применять данный алгоритм для нахождения НОД трех чисел и НОК двух чисел.

Домашнее задание.

1. Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:

НОД(А, B, С) = НОД(НОД(А, В), С)

2.Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

А  В = НОД(А, В)  НОК(А, В)

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 ВыводM

Cлайд 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 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.

Постановка Задачи Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел. Вспомним математику. Наибольший общий делитель двух натуральных чисел это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 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.">

Слайд 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 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.

Посмотреть все слайды

Класс: 6

Цели урока:

• закрепить алгоритм нахождения наибольшего общего делителя с помощью разложения на множители;
• повторить сопутствующие определения и понятия;
• познакомить учащихся с алгоритмом Евклида;
• формировать навыки математической культуры

Оборудование: компьютер, проектор, экран.

Ход урока

1. Орг.момент (проверка готовности учащихся к уроку, отметка отсутствующих) (1 мин)

2. Устная работа: (6 мин)

1. Замените произведение степенью:

г) а*а*а*а*а

1. Вычислите: 2 3 ; 5 2 ; 3 3 ; 10 4 .
2. Найдите значение выражения: (3?3?5?11): (3?11). Какой вывод можно сделать?
3. Выполните деление a на b , если а=170, b=35. Запишите равенством, чему равно а.

Данное равенство записать в общем виде: а будет делимым, а b - делителем. Пусть частное равно q, а остаток r, тогда: а = bq + r , причем q может быть как натуральным числом, так и нулем. Любым ли числом может быть r? [ r - натуральное число, причем 0 < r < b .] Что можно сказать о числах а и b, если r = 0? Деление нацело - частный случай деления с остатком.

4. Выясните и объясните, делится ли без остатка число а на число b, если:

а) а = 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. Поступаем следующим образом (