АЛГОРИТМ ЕВКЛИДА

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

АЛГОРИТМ ЕВКЛИДА Евклид (365-300 до. н. э.) Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание».

НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. Вычисление НОД НОД(a, b)= НОД(a­b, b)= НОД(a, b­ НОД(a, b)= НОД(a­b, b)= НОД(a, b­ a) a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. Пример : НОД (18, 45) = НОД (18, 45­18) = НОД (18, 27)= НОД (18, 9)  = =НОД(9,9)=9

48 ШАГ Операция M N 1 2 3 4 5 6 7 8 9 10 11 12 13 Ввод M Ввод N MN M>N M:=M-N MN M>N M:=M-N MN M>N N:=N-M MN M>N 30 12 18 6 Условие 4818, да 48>18, да 3018, да 30>18, да 1218, да 12>18, нет 126, да 12>6, да

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.Выполните на компьютере программу 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)