Содержание
Алгоритм Евклида- это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.
Скачать:
| Вложение | Размер |
|---|---|
| algoritm_evklida.pptx | 274.93 КБ |
| konspekt.docx | 56.55 КБ |
Предварительный просмотр:
Подписи к слайдам:
АЛГОРИТМ ЕВКЛИДА ЕВКЛИД , древнегреческий математик. Работал в Александрии в 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 m<>n do begin if m>n then m:=m-n else n := n-m ; end; write (‘nod=’,m); readln end.
0.Выполните на компьютере программу Evkl >
Предварительный просмотр:
Тема: «Алгоритм Евклида»
- Образовательные:
- научиться применять алгоритм Евклида для нахождения НОД двух и трех чисел
- закрепить навыки по использованию алгоритмических структур «Ветвление» и «Цикл»
- получить опыт написания и отладки программ на языке программирования Паскаль
- Воспитательная:
- формирование самостоятельности и ответственности при изучении нового материала
- Развивающая:
- развитие внимания и аналитического мышления
- Организационный момент
- Актуализация знаний
- Объяснение новой темы
- Практическая часть
- Подведение итогов урока
- Домашнее задание.
Организационный момент
Приветствие. Кто отсутствует. Число. Тема урока. Вопросы по домашнему заданию.
Актуализация знаний.
Какие типы алгоритмических структур вы знаете?
Какая структура называется линейной? (Бл-сх)
Какая структура называется разветвляющейся? (Бл-сх)
Какая структура называется циклической? (Бл-сх)
Какие виды циклов вы знаете?
Как реализуется на языке программирования Паскаль цикл с известным числом повторений?
Как реализуется на языке программирования Паскаль цикл с неизвестным числом повторений?
Объяснение новой темы (презентация)
Идея алгоритма Евклида
Идея этого алгоритма основана на:
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) заменить большее число разностью большего и меньшего из чисел;
Презентация была опубликована 6 лет назад пользователемИнесса Шишманова
Похожие презентации
Презентация на тему: " АЛГОРИТМ ЕВКЛИДА (нахождение наибольшего общего делителя (НОД) двух натуральных чисел)" — Транскрипт:
1 АЛГОРИТМ ЕВКЛИДА (нахождение наибольшего общего делителя (НОД) двух натуральных чисел)
2 Входные данные: m, n – натуральные числа; Выходные данные: nod – наибольший общий делитель этих двух чисел; Вспомогательные данные: x, y – хранят значения m, n для их дальнейшего изменения
y x:=x-yy:=y-x Вывод nod конец Ввод m, n x:=m y:=n данет да Nod:=x нет Паскаль-программа Program nod; Var m,n,x,y,nod: word; BEGIN WriteLn(Введите два числа:); readLn(m,n); x:=m; y:=n; While xy Do If x > y Then x:=x-y else y:=y-x; N" title="БЛОК-СХЕМА н xy x>y x:=x-yy:=y-x Вывод nod конец Ввод m, n x:=m y:=n данет да Nod:=x нет Паскаль-программа Program nod; Var m,n,x,y,nod: word; BEGIN WriteLn(Введите два числа:); readLn(m,n); x:=m; y:=n; While xy Do If x > y Then x:=x-y else y:=y-x; N" > 3 БЛОК-СХЕМА н xy x>y x:=x-yy:=y-x Вывод nod конец Ввод m, n x:=m y:=n данет да Nod:=x нет Паскаль-программа Program nod; Var m,n,x,y,nod: word; BEGIN WriteLn(Введите два числа:); readLn(m,n); x:=m; y:=n; While xy Do If x > y Then x:=x-y else y:=y-x; Nod:=x; WriteLn(НОД чисел,m, и,n,равен,nod:5); END. y x:=x-yy:=y-x Вывод nod конец Ввод m, n x:=m y:=n данет да Nod:=x нет Паскаль-программа Program nod; Var m,n,x,y,nod: word; BEGIN WriteLn(Введите два числа:); readLn(m,n); x:=m; y:=n; While xy Do If x > y Then x:=x-y else y:=y-x; N"> y x:=x-yy:=y-x Вывод nod конец Ввод m, n x:=m y:=n данет да Nod:=x нет Паскаль-программа Program nod; Var m,n,x,y,nod: word; BEGIN WriteLn(Введите два числа:); readLn(m,n); x:=m; y:=n; While xy Do If x > y Then x:=x-y else y:=y-x; Nod:=x; WriteLn(НОД чисел,m, и,n,равен,nod:5); END."> y x:=x-yy:=y-x Вывод nod конец Ввод m, n x:=m y:=n данет да Nod:=x нет Паскаль-программа Program nod; Var m,n,x,y,nod: word; BEGIN WriteLn(Введите два числа:); readLn(m,n); x:=m; y:=n; While xy Do If x > y Then x:=x-y else y:=y-x; N" title="БЛОК-СХЕМА н xy x>y x:=x-yy:=y-x Вывод nod конец Ввод m, n x:=m y:=n данет да Nod:=x нет Паскаль-программа Program nod; Var m,n,x,y,nod: word; BEGIN WriteLn(Введите два числа:); readLn(m,n); x:=m; y:=n; While xy Do If x > y Then x:=x-y else y:=y-x; N">
- Скачать презентацию (0.25 Мб) 61 загрузок 4.0 оценка
Рецензии
Аннотация к презентации
Презентация для школьников на тему «Алгоритм Евклида» по математике. pptCloud.ru — удобный каталог с возможностью скачать powerpoint презентацию бесплатно.
Содержание
АЛГОРИТМ ЕВКЛИДА
Алгоритм Евклида — это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. Евклид (365-300 до. н. э.) Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание».
Вычисление НОД
НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. НОД(a,b)= НОД(a-b, b)= НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (18, 45)= НОД (18, 45-18)= НОД (18, 27)=НОД (18, 9)= =НОД(9,9)=9 Пример:
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.
0.Выполните на компьютере программу Evkl >
ЕВКЛИД, древнегреческий математик. Работал в Александрии в 3 в. до н. э. Главный труд «Начала» (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.
«>