Алгоритм Евклида- это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.
Скачать:
Предварительный просмотр:
Подписи к слайдам:
АЛГОРИТМ ЕВКЛИДА ЕВКЛИД , древнегреческий математик. Работал в Александрии в 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.Выполните на компьютере программу 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 ) Задачи
Источник: nsportal.ru
Алгоритм Евклида для нахождения НОД двух чисел
Алгоритм Евклида (или алгоритм Евклида) — это метод эффективного нахождения наибольшего общего делителя (НОД) двух чисел. НОД двух целых чисел, X а также Y , является наибольшим числом, которое делит оба X а также Y не оставляя остатка.
Euclid(30, 50) = 10
Euclid(2740, 1760) = 20
The Евклидов алгоритм основывается на том принципе, что наибольший общий делитель двух чисел не изменится, если большее число заменить его разностью с меньшим числом.
20 Цикл while Алгоритм Евклида Python
Например, 21 — это НОД 252 и 105 ( 252 = 21 × 12 а также 105 = 21 × 5 ), а то же число 21 также является НОД 105 и 147 ( 147 = 252 — 105 ).
Поскольку эта замена уменьшает большее из двух чисел, повторение этого процесса дает последовательно меньшие пары чисел, пока два числа не станут равными. Когда это происходит, они являются GCD исходных двух чисел.
Следующая программа на C демонстрирует это:
Источник: www.techiedelight.com
Алгоритм евклида для нахождения нод программа
Этот волшебный алгоритм я узнал еще давно, наверное, где-то в 3-4 классе начальной школы, и был потрясен до глубины души его простотой. Он описывался вот таким образом:
int NOD(int a, int b) < return b == 0 ? a : NOD(b, a % b); >
Сказать то, что я был в шоке — мало. Я был в ступоре! Я не мог понять, каким именно таким образом с помощью всего лишь, можно сказать, одной строки высчитывается наибольший общий делитель! Как так? Я думал, что нужно перебирать все числа подряд, чтобы найти, а тут такой простой алгоритм это делает без проблем.
Это была настоящая магия, понять которую можно только лишь магам, или богам.
И совершенно недавно, в возрасте 31 года, я понял. Я понял только лишь в этом возрасте. И попытаюсь объяснить, как именно это работает.
Итак, начнем с самого-самого простого, с разложения числа. Нам нужно найти НОД от a, b, это пишется так НОД(a, b) = d, где a и b — это числа, которые мы ищем, а «d» — это и есть наибольший общий делитель. Давайте сделаем так. Мы число «a» представим в виде вот такой формулы:
Почему именно такой? Ответ простой – просто так нужно, если мы не сделаем такое представление, то ничего не докажем и не выведем. И это будет работать, спросите вы? Конечно! Абсолютно любое целое число «a» можно разложить в эту формулу.
Пример: возьмем числа a = 10, b = 3, просто для проверки. Чтобы найти q и r, требуется сделать очень простые вещи:
Источник: www.neurofox.ru