Презентация по информатике на тему Алгоритм Евклида

АЛГОРИТМ ЕВКЛИДАЕВКЛИД, древнегреческий математик. Работал в Александрии в 3 в. до н. э. Главный труд "Начала" (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов.Оказал огромное влияние на развитие математики.Работы по астрономии, оптике, теории музыки.


АЛГОРИТМ ЕВКЛИДААлгоритм Евклида - это алгоритм нахождения наибольшего общего делителя двух целых неотрицательных чисел.Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». НОД - наибольший общий делитель двух натуральных чисел – это самое большое натуральное число, на которое оба исходных числа делятся нацело (без остатка).Например, у чисел 12 и 18 имеются общие делители: 2,3,6. НОД (12,18) = 6.
Вычисление НОДНОД(m, n)= НОД(m-n, n)= НОД(m, n-m)НОД (m,m) = mСравнить числа, если они не равны, то заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Пример :НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27)= = НОД (18, 27-18) = НОД (18, 9) = НОД(9, 9) = 9НОД (7,7) = 7Задание. Подсчитайте НОД (165,66).

{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}ШАГОперацияMNУсловие1Ввод M482Ввод N183MN4818, да4M>N48>18, да5M:=M-N306MN3018, да7M>N30>18, да8M:=M-N129MN1218, да10M>N12>18, нет11N:=N-M612MN126, да13M>N12>6, да14M:=M-N615MN66, нет16Вывод Mppt_y
ppt_y
ppt_y
ppt_y
ppt_y
ppt_y
ppt_y
ppt_y
ppt_y
ppt_y
ppt_y
ppt_y
ppt_y
program Evklid;var m, n: integer;beginwriteln (Введи 2 числа');readln (m,n); while m<>n do begin if m>n then m:=m-n else n:=n-m; end; write (‘НОД=',m);end.