Алгоритм евклида нод

Алгоритм Евклида — это способ нахождения наибольшего общего делителя (НОД) двух целых чисел. Оригинальная версия алгоритма, когда НОД находится вычитанием, была открыта Евклидом (III в. до н. э). В настоящее время чаще при вычислении НОД алгоритмом Евклида используют деление, так как данный метод эффективнее.

Вычисление НОД делением

Наибольший общий делитель пары чисел – это самое большое число, которое нацело делит оба числа пары. Пусть требуется вычислить НОД для чисел 108 и 72. Алгоритм вычисления делением будет таковым:

  1. Разделим большее число (делимое) на меньшее (делитель): 108 / 72 = 1, остаток 36.
  2. Поскольку остаток не был равен нулю, то сделаем делитель делимым, а остаток – делителем: 72 / 36 = 2, остаток 0.
  3. Когда остаток равен нулю, то делитель является искомым НОД для пары заданных чисел. То есть НОД(108, 72) = 36. Действительно, 108 / 36 = 3 и 72 / 36 = 2.

В данном алгоритме деление повторяется до тех пор, пока остаток не станет равным нулю. Когда он таковым становится, НОДом является делитель последнего деления. Например, требуется найти НОД(106, 16):

  1. 106 / 16 = 6, остаток 10
  2. 16 / 10 = 1, остаток 6
  3. 10 / 6 = 1, остаток 4
  4. 6 / 4 = 1, остаток 2
  5. 4 / 2 = 2, остаток 0
  6. НОД(106, 16) = 2

Вычисление НОД вычитанием

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

Пусть требуется найти НОД(108, 72):

  1. 108 — 72 = 36
  2. 72 — 36 = 36
  3. 36 — 36 = 0
  4. НОД(108, 72) = 36

Найдем НОД(44, 60):

  1. 60 — 44 = 16
  2. 44 — 16 = 28
  3. 28 — 16 = 12
  4. 16 — 12 = 4
  5. 12 — 4 = 8
  6. 8 — 4 = 4
  7. 4 — 4 = 0
  8. НОД(44, 60) = 4

Данный алгоритм иногда описывают по-другому. Вычитание заканчивают раньше, на шаге, когда одно число нацело делит другое. То есть комбинируют вычитание с проверкой делимости. Тогда нахождение НОД для 44 и 60 будет выглядеть так:

  1. Делит ли 44 нацело 60? Нет. 60 — 44 = 16.
  2. Делит ли 16 нацело 44? Нет. 44 — 16 = 28.
  3. Делит ли 16 нацело 28? Нет. 28 — 16 = 12.
  4. Делит ли 12 нацело 16? Нет. 16 — 12 = 4.
  5. Делит ли 4 нацело 12? Да. Значит, НОД(44, 60) = 4.

Обратите внимание, НОДом является не частное, а делитель. Если в примере мы разделим 12 на 4, то получим частное 3. Но это не НОД.

Доказательство алгоритма Евклида

Примем во внимание факт, что если одно натуральное число из пары нацело делит другое, то их НОД будет равен меньшему из них. Записать это можно так:

если a / b нацело, то НОД(a, b) = b. Например, НОД(15, 5) = 5.

Таким образом, если в конечном итоге мы приходим к паре чисел, одно из которых делит нацело другое, то меньшее будет для обоих наибольшим общим делителем. Именно такая пара чисел ищется алгоритмом Евклида: одно число нацело делит другое.

Второй факт. Требуется доказать, что если одно число больше другого, то их наибольший общий делитель равен наибольшему общему делителю для меньшего числа из пары, и разнице большего и меньшего чисел. Это можно записать так:

если a < b, то НОД(a, b) = НОД(a, b — a).

Доказать, что НОД(a, b) = НОД(a, b — a) можно следующим образом. Пусть b — a = c. Если какое-либо число x делит нацело a и b, то оно будет также делить нацело c. Ведь если a и b различны, то делитель в них укладывается целое, но разное число раз. И если вычесть одно из другого, то делитель также должен укладываться целое число раз в полученную разность.

Если последовательно уменьшать a и b, то рано или поздно придем к такому значению меньшего из них, которое нацело делит большее. Меньшее в такой паре будет наибольшим общим делителем для исходной пары натуральных чисел. В этом и заключается алгоритм Евклида.

Содержание

Алгоритм Евклида

Наибольший общий делитель

Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.

Вспомним математику. Наибольший общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:

НОД(12, 18) = 6.

Обозначим исходные данные как М u N. Постановка задачи выглядит следующим образом:
Дано: М, N
Найти: НОД(М, N).

В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.

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

Идея этого алгоритма основана на том свойстве, что если M>N, то

НОД(М, N) = НОД(М — N, N).

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

Легко доказать это свойство. Пусть К — общий делитель М u N (M> N). Это значит, что М = mК, N = nК, где m, n — натуральные числа, причем m > n.

Нахождение нод по алгоритму Евклида и с помощью разложения на простые множители.

Тогда М — N = К(m — n), откуда следует, что К — делитель числа М — N. Значит, все общие делители чисел М и N являются делителями их разности М — N, в том числе и наибольший общий делитель.

Второе очевидное свойство:

НОД(М, М) = М.

Для «ручного» счета алгоритм Евклида выглядит так:

1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;

2) заменить большее число разностью большего и меньшего из чисел;

3) вернуться к выполнению п. 1.

Рассмотрим этот алгоритм на примере М=32, N=24:

Получили: НОД(32, 24) =НОД(8, 8) = 8, что верно.

Описание алгоритма Евклида блок-схемой

На рис. 3.12 приведена блок-схема алгоритма Евклида.

Рис. 3.12. Блок-схема алгоритма Евклида

Структура алгоритма — цикл-пока с вложенным ветвлением. Цикл повторяется, пока значения М и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

А теперь посмотрите на трассировочную таблицу алгоритма для исходных значений М = 32, N = 24.

Шаг Операция M N Условие
1 ввод М 32    
2 ввод N   24  
3 M ¹ N     32 ¹ 24, да
4 M>N     32>24, да
5 M:=M-N 8    
6 M ¹ N     8 ¹ 24, да
7 M>N     8>24, нет
8 N:=N-M   16  
9 M ¹ N     8 ¹ 16, да
10 M>N     8>16, нет
11 N:=N-M   8  
12 M ¹ N     8 ¹ 8, нет
13 вывод M 8    
14 конец      

В итоге получился верный результат.

Программа на АЯ и на Паскале

Запишем алгоритм на АЯ и программу на Паскале.

алг Евклид
цел М, N
нач
     вывод » Введите М и N» ввод М, N
     пока М N, повторять
     нц
          если M>N
          то M:=M-N
          иначе N:=N-M
          кв
     кц
     вывод «НОД=»,М
кон
Program Evklid;
var M, N: integer;
begin
     writeln(‘Введите М и N’);
     readln(M, N);
     while M<>N do
          begin
               if M>N
               then M:=M-N
               else N:=N-M
     end;
     write(‘Н0Д=’,М)
end.

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

1.

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

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

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

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

А × В = НОД(А, В) × НОК(А, В).

Наибольший общий делитель чисел – это наибольшее число, на которое делятся все заданные числа.

Алгоритм Евклида

Алгоритм поиска НОД

Вычисление НОД похоже на поиск НОК. Чтобы найти наибольший общий делитель, нужно использовать следующий алгоритм:

  1. Разложить все числа на простые множители, используя признаки делимости чисел.
  2. Найти совпадающие множители во всех числах и выписать их.
  3. Перемножить совпадающие множители.

Если среди множителей чисел не были найдены одинаковые, числа являются взаимно простыми.

Примеры поиска наибольшего общего делителя

Рассмотрим, как найти НОД с помощью алгоритма на нескольких примерах.

Пример 1:

Найдите наибольший общий делитель чисел 420 и 990.

Решение:

Разложим оба числа на простые множители:

Получили, что:

420 = 2 ⋅ 2 ⋅ 3 ⋅ 5 ⋅ 7

990 = 2 ⋅ 3 ⋅ 3 ⋅ 5 ⋅ 11

Выпишем все совпадающие множители для обоих чисел и перемножим их:

Ответ: 30

Пример 2:

Найдите наибольший общий делитель чисел 588 и 1820.

Решение:

Разложим оба числа на простые множители:

Получили, что:

588 = 2 ⋅ 2 ⋅ 3 ⋅ 7 ⋅ 7

1820 = 2 ⋅ 2 ⋅ 5 ⋅ 7 ⋅ 13

Выпишем все совпадающие множители для обоих чисел и перемножим их:

Ответ: 28

Пример 3:

Найдите наибольший общий делитель чисел 1000 и 3267.

Решение:

Разложим оба числа на простые множители:

Получили, что:

1000 = 2 ⋅ 2 ⋅ 2 ⋅ 5 ⋅ 5 ⋅ 5

3267 = 3 ⋅ 3 ⋅ 3 ⋅ 11 ⋅ 11

Совпадающих множителей у этих 2 чисел нет, поэтому они являются взаимно простыми, то есть

Ответ: 1

На главную

Школьная алгебра. Школьная геометрия

Наибольший общий делитель. Алгоритм Евклида

Алгоритм Евклида, НОД. Пример

Используя алгоритм Евклида, найдите нод для чисел 126 и 15.

Пример алгоритма Евклида рассмотрим по шагам.

1. 126 > 15, будем делить 126 на 15.

2. Делим 126 на 15, получаем 8 и остаток 6:

126 : 15 = 8
остаток 6

Перепишем это так:

126 = 15 * 8 + 6

3. Делим число 15 на остаток 6, получим частное 2 и остаток 3:

15 : 6 = 2
остаток 3

Это можно записать так:

15 = 6 * 2 + 3

4. Делим 6 на остаток 3:

6 : 3 = 2
остаток 0

Это можно записать так:

6 = 3 * 2 + 0 =
3 * 2

5. Так как мы получили ноль в остатке, деление останавливаем. НОД равен 3.

Нахождение НОД по алгоритму Евклида и с помощью разложения на простые множители.

Перепишем алгоритм нахождения НОД без пояснений:

1. 126 = 15 * 8 + 6
2. 15 = 6 * 2 + 3
3. 6 = 3 * 2

Ответ:

НОД(126, 15) = 3

добавлено: 10 Jun 2008 17:58
редактировано: 17 Oct 2012 14:55

Расширенный алгоритм Евклида

В то время как «обычный» алгоритм Евклида просто находит наибольший общий делитель двух чисел и , расширенный алгоритм Евклида находит помимо НОД также коэффициенты и такие, что:

Т.е.

Алгоритм Евклида. Наибольший общий делитель.

он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа.

Алгоритм

Внести вычисление этих коэффициентов в алгоритм Евклида несложно, достаточно вывести формулы, по которым они меняются при переходе от пары к паре (знаком процента мы обозначаем взятие остатка от деления).

Итак, пусть мы нашли решение задачи для новой пары :

и хотим получить решение для нашей пары :

Для этого преобразуем величину :

Подставим это в приведённое выше выражение с и и получим:

и, выполняя перегруппировку слагаемых, получаем:

Сравнивая это с исходным выражением над неизвестными и , получаем требуемые выражения:

Реализация

  int gcd (int a, int b, int& x, int& y){if(a ==0){ x =0; y =1;return b;}int x1, y1;int d = gcd (b%a, a, x1, y1); x = y1 -(b / a)* x1; y = x1;return d;}

Это рекурсивная функция, которая по-прежнему возвращает значение НОД от чисел и , но помимо этого — также искомые коэффициенты и в виде параметров функции, передающихся по ссылкам.

База рекурсии — случай .

Тогда НОД равен , и, очевидно, требуемые коэффициенты и равны и соответственно. В остальных случаях работает обычное решение, а коэффициенты пересчитываются по вышеописанным формулам.

Расширенный алгоритм Евклида в такой реализации работает корректно даже для отрицательных чисел.

Литература

 

 


powered by e-maxx.ru

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *