Алгоритм Евклида — реализация на Python
Алгоритм Евклида — это алгоритм, который используется для нахождения наибольшего делителя двух целых чисел. Он часто используется как в обучающих целях, так и в прикладных задачах.
Существует несколько видов алгоритма: обычный, расширенный и бинарный. Все виды алгоритма Евклида легко реализуются на языке программирования Python.
Классический алгоритм Евклида
Этот вид алгоритма Евклида является самым простым, он был придуман более 1300 лет назад. С появлением электронно-вычислительных машин расширились возможности по применению алгоритма Евклида, возникли новые более эффективные его реализации.
Алгоритм состоит из определенного количества шагов, количество которых зависит от размера входных данных.
Реализация на Python
Существует несколько реализаций классического алгоритма Евклида, которые основаны на использовании различных операторов и возможностей языка Python (остаток от деления, вычитание, рекурсия). Эти реализации отличаются незначительно, сильные различия в эффективности наблюдаются только при специфических входных данных.
Реализация с помощью остатка от деления
Идея такой реализации достаточна проста, алгоритм уменьшает числа до тех пор, пока одно из них не станет равно нулю, а другое искомому делителю. Для этого используется цикл while , в котором большее число делится на меньшее и становится равным остатку от деления. Таким образом, функция вернёт наибольший общий делитель (НОД) её двух аргументов.
Код алгоритма Евклида на Python:
Так как одно из чисел всегда становится равным нулю, то функция всегда будет возвращать делитель, благодаря логическому оператору или, который используется вместе с return .
В каждой новой итерации большее число становится меньшим и наоборот. Возьмём числа 168 и 105 и распишем работу программы вручную:
- 1 итерация:
168 % 105 = 63
105 - 2 итерация:
63
105 % 63 = 42 - 3 итерация:
63 % 42 = 21
42 - 4 итерация:
42 % 21 = 0
21
После 4 итерации алгоритм завершает свою работу, так как одно из чисел равно нулю, второе же число равно наибольшему общему делителю, в нашем случае это 21. Проверим работу программы:
Реализация с помощью вычитания
Идея этой реализации схожа с предыдущей, однако здесь числа уменьшаются до нуля и делителя с помощью вычитания.
Код вычисления НОД на Python:
Также распишем работу программы с числами 168 и 105:
- 1 итерация:
168 — 105 = 63
105 - 2 итерация:
63
105 — 63 = 42 - 3 итерация:
63 — 42 = 21
42 - 4 итерация:
21
42 — 21 = 21 - 5 итерация:
21 — 21 = 0
21
Видно, что до 4 итерации результаты работы обоих версий алгоритма полностью совпадают. Отличия начинаются, когда в 4 итерации вместо 0 и 21, получается числа 21 и 21, из-за чего в алгоритме с вычитанием добавляется дополнительная итерация, но это не значит, что он работает менее эффективнее.
Проверка работы программы:
Реализация с помощью рекурсии
Суть алгоритма схожа с реализацией через остаток от деления, однако вместо цикла while используется рекурсия.
Код программы на Python нахождения НОД с помощью рекурсии:
Первое, что стоит заметить, на ноль проверяется только num1 . Важно понять, что числа постоянно меняются местами. В качестве первого числа в рекурсивный вызов функции передаётся num2 % num1 , вспомним 4 итерацию в алгоритме через остаток от деления:
- 4 итерация:
42 % 21 = 0 — num1
21 — num2
То есть рекурсивный алгоритм проверит число num1 на ноль, получит True и вернёт значение num2 , которое и будет являться наибольшим общим делителем.
Особенности алгоритма: простые числа
Если два переданных числа не имеют общих делителей, то алгоритм возвращает единицу. Действительно, ведь каждое число делится на единицу. Например, числа 35 и 18 не имеют общих делителей:
- 35 = 5 * 7 * 1
- 18 = 2 * 9 * 1 = 3 * 6 * 1
Алгоритм будет возвращать единицу, если оба переданных числа являются простыми и не равны друг другу. Простые числа делятся только на себя и на единицу.
Если алгоритм получает на вход одно простое число, это не значит, что он обязательно вернет единицу:
- 5 и 15: число 5 является простым, а 15 — нет, алгоритм вернет наибольший общий делитель 5.
- 5 и 21: число 5 — простое, а 21 — нет, будет возвращена единица, потому что 21 не делится на 5.
- 3 и 21: число 3 — простое, 21 — нет, будет возвращено число 3, потому что 21 делится на 3.
Расширенный алгоритма Евклида
Расширенным алгоритм называется не из-за более высокой скорости работы или более сложной реализации, а потому что он позволяет извлекать из входных данных дополнительную информацию.
Расширенный алгоритм также находит наибольший общий делитель, а ещё он определяет два коэффициента x и y, такие что:
ax + by = gcd(a,b), где gcd – это функция по нахождения НОД.
Иными словами, алгоритм находит наибольший делитель и его линейное представление.
gcd – это аббревиатура, которую часто используют для обозначения функции по назначению НОД:
- g – Greatest (наибольший);
- c – Common (общий);
- d – Divisor (делитель).
Реализация на Python
Код программы выглядит так:
Проверяем работу кода:
Подставим полученные коэффициенты в формулу, тогда:
Действительно, коэффициенты и делитель найдены правильно. Но как работает алгоритм?
Сначала проверяется, равно ли первое число нулю, если это так, то второе число является делителем, а коэффициенты равны 0 и 1, так как «num1 * x + num2 * y = y» в том случае, если y = 1, а левое произведение равно нулю.
Функция возвращает три числа: делитель, коэффициент x и коэффициент y. Для её реализации используется рекурсия, делитель получается тем же образом, что и в классическом рекурсивным алгоритме, а коэффициенты рекурсивно вычисляются по формулам:
- x = y — (num2 // num1) * x
- y = x
Бинарный алгоритм Евклида
Суть бинарного алгоритма точно такая же — найти наибольший делитель. От классического он отличается только способом реализации.
Сложность алгоритма по прежнему определяется функций O(h 2 ), однако реальные тесты показывают, что бинарный алгоритм эффективнее классического на 60%, это обусловлено различиями в реализациях обычных арифметических операций и сдвигов.
Реализация на Python
Бинарный алгоритм имеет довольно сложную реализацию по сравнению со всеми предыдущими, однако это окупается его эффективностью.
Код на Python:
Результат выполнения не будет отличаться от результатов, полученных другими реализациями.
Тест скорости выполнения
Для выполнения теста воспользуемся функцией monotonic модуля time. Подробнее про неё и про то, как засечь время выполнения программы описано здесь.
Мы будем делать проверку, используя функцию выше описанного бинарного алгоритма Евклида и описанную в самом начале функцию классического.
Код проверки следующий:
Результат теста выглядит следующим образом:
Из результатов видно, что реализация классического алгоритма на Python быстрее, чем бинарного. Так что лучше на Python использовать классический алгоритм Евклида, а если программировать на C++ и важна скорость выполнения, то тогда использовать бинарный.
Заключение
Алгоритм Евклида позволяет эффективно находить общие делители чисел. За много лет его существования было придумано несколько различных видов, которые могут отличаться по способу реализации и эффективности.
Любой вид алгоритма Евклида можно реализовать на языке Python без использования сторонних библиотек.
Как найти НОД нескольких чисел?
Дано n целых чисел. Требуется найти такое наибольшее целое число, на которое делятся все эти n чисел.
У меня есть код для нахождения нод двух чисел, но как реализовать нахождение нод нескольких чисел?
math.gcd Changed in version 3.9: Added support for an arbitrary number of arguments. Formerly, only two arguments were supported.
До версии 3.9, но выше 3.5 можно скомбинировать так:
Для версии ниже 3.5:
Берем первые два числа. Ищем НОД (назовем его nod ). Берем третье число, ищем НОД к нему и nod . Повторять, пока числа не закончатся.
Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.3.11.43304
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Как найти нод двух чисел python
In Python, math module contains a number of mathematical operations, which can be performed with ease using the module. math.gcd() function compute the greatest common divisor of 2 numbers mentioned in its arguments.
Syntax: math.gcd(x, y) Parameter: x : Non-negative integer whose gcd has to be computed. y : Non-negative integer whose gcd has to be computed. Returns: An absolute/positive integer value after calculating the GCD of given parameters x and y. Exceptions : When Both x and y are 0, function returns 0, If any number is a character, Type error is raised.
Time Complexity: O(1)
Auxiliary Space: O(1)
VladHub18 / FunctionsTask 8.py
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| a = int ( input ()) |
| b = int ( input ()) |
| def NOD ( a , b ): |
| while a != b : |
| if a > b : |
| a = a — b |
| else : |
| b = b — a |
| return a |
| print ( NOD ( a , b )) |
| def NOK ( a , b ): |
| a = a * b // NOD ( a , b ) |
| return a |
| print ( NOK ( a , b )) |
А если нужно отделить эти две программы, то есть отдельно нахождение НОД и НОК.
Пытаюсь переписать код для нахождения НОК, но не получается. Вариант с вызовом функции НОДа отпадает.
Footer
© 2023 GitHub, Inc.
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.