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

Алгоритм Евклида — реализация на Python

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

Существует несколько видов алгоритма: обычный, расширенный и бинарный. Все виды алгоритма Евклида легко реализуются на языке программирования Python.

Классический алгоритм Евклида

Этот вид алгоритма Евклида является самым простым, он был придуман более 1300 лет назад. С появлением электронно-вычислительных машин расширились возможности по применению алгоритма Евклида, возникли новые более эффективные его реализации.

Алгоритм состоит из определенного количества шагов, количество которых зависит от размера входных данных.

Сложность алгоритма выражается функцией O(h2), где h – это количество десятичных цифр в наименьшем числе, наибольший делитель которых ищется алгоритмом.

Реализация на Python

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

Реализация с помощью остатка от деления

Идея такой реализации достаточна проста, алгоритм уменьшает числа до тех пор, пока одно из них не станет равно нулю, а другое искомому делителю. Для этого используется цикл while , в котором большее число делится на меньшее и становится равным остатку от деления. Таким образом, функция вернёт наибольший общий делитель (НОД) её двух аргументов.

Код алгоритма Евклида на Python:

def gcd_rem_division(num1, num2): while num1 != 0 and num2 != 0: if num1 >= num2: num1 %= num2 else: num2 %= num1 return num1 or num2

Так как одно из чисел всегда становится равным нулю, то функция всегда будет возвращать делитель, благодаря логическому оператору или, который используется вместе с 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. Проверим работу программы:

a = gcd_rem_division(168, 105) print(a) # Выведет 21

Реализация с помощью вычитания

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

Код вычисления НОД на Python:

def gcd_subtraction(num1, num2): while num1 != 0 and num2 != 0: if num1 >= num2: num1 -= num2 else: num2 -= num1 return num1 or num2

Также распишем работу программы с числами 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, из-за чего в алгоритме с вычитанием добавляется дополнительная итерация, но это не значит, что он работает менее эффективнее.

Проверка работы программы:

a = gcd_subtraction(168, 105) print(a) # Выведет 21

Реализация с помощью рекурсии

Суть алгоритма схожа с реализацией через остаток от деления, однако вместо цикла while используется рекурсия.

Код программы на Python нахождения НОД с помощью рекурсии:

def gcd_recursion(num1, num2): if num1 == 0: return num2 return gcd_recursion(num2 % num1, num1)

Первое, что стоит заметить, на ноль проверяется только num1 . Важно понять, что числа постоянно меняются местами. В качестве первого числа в рекурсивный вызов функции передаётся num2 % num1 , вспомним 4 итерацию в алгоритме через остаток от деления:

То есть рекурсивный алгоритм проверит число num1 на ноль, получит True и вернёт значение num2 , которое и будет являться наибольшим общим делителем.

Особенности алгоритма: простые числа

Если два переданных числа не имеют общих делителей, то алгоритм возвращает единицу. Действительно, ведь каждое число делится на единицу. Например, числа 35 и 18 не имеют общих делителей:

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

Если алгоритм получает на вход одно простое число, это не значит, что он обязательно вернет единицу:

• 5 и 15: число 5 является простым, а 15 — нет, алгоритм вернет наибольший общий делитель 5.
• 5 и 21: число 5 — простое, а 21 — нет, будет возвращена единица, потому что 21 не делится на 5.
• 3 и 21: число 3 — простое, 21 — нет, будет возвращено число 3, потому что 21 делится на 3.

Исходя из этого, можно сказать, что алгоритм Евклида со 100%-ой вероятностью возвращает единицу в том случае, если на вход переданы два простых числа не равных друг другу.

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

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

Расширенный алгоритм также находит наибольший общий делитель, а ещё он определяет два коэффициента x и y, такие что:

ax + by = gcd(a,b), где gcd – это функция по нахождения НОД.

Иными словами, алгоритм находит наибольший делитель и его линейное представление.

gcd – это аббревиатура, которую часто используют для обозначения функции по назначению НОД:

Реализация на Python

Код программы выглядит так:

def gcd_extended(num1, num2): if num1 == 0: return (num2, 0, 1) else: div, x, y = gcd_extended(num2 % num1, num1) return (div, y - (num2 // num1) * x, x)

Проверяем работу кода:

a = gcd_extended(426, 334) print(f'Делитель равен , x = , y = ') Делитель равен 2, x = 69, y = -88

Подставим полученные коэффициенты в формулу, тогда:

Действительно, коэффициенты и делитель найдены правильно. Но как работает алгоритм?

Сначала проверяется, равно ли первое число нулю, если это так, то второе число является делителем, а коэффициенты равны 0 и 1, так как «num1 * x + num2 * y = y» в том случае, если y = 1, а левое произведение равно нулю.

Функция возвращает три числа: делитель, коэффициент x и коэффициент y. Для её реализации используется рекурсия, делитель получается тем же образом, что и в классическом рекурсивным алгоритме, а коэффициенты рекурсивно вычисляются по формулам:

Бинарный алгоритм Евклида

Суть бинарного алгоритма точно такая же — найти наибольший делитель. От классического он отличается только способом реализации.

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

Сложность алгоритма по прежнему определяется функций O(h 2 ), однако реальные тесты показывают, что бинарный алгоритм эффективнее классического на 60%, это обусловлено различиями в реализациях обычных арифметических операций и сдвигов.

Однако ускорение бинарного по сравнению с классическим алгоритмом справедливо не для кода написанного на Python. Ниже, после описания его реализации проведём тест скорости выполнения для Python.

Реализация на Python

Бинарный алгоритм имеет довольно сложную реализацию по сравнению со всеми предыдущими, однако это окупается его эффективностью.

Код на Python:

def binary_gcd(num1, num2): shift = 0 # Если одно из чисел равно нулю, делитель - другое число if num1 == 0: return num2 if num2 == 0: return num1 # Если num1 = 1010, а num2 = 0100, то num1 | num2 = 1110 # 1110 & 0001 == 0, тогда происходит сдвиг, который фиксируется в shift while (num1 | num2) & 1 == 0: shift += 1 num1 >>= 1 num2 >>= 1 #Если True, значит num1 - четное, иначе - нечетное while num1 & 1 == 0: # если нечетное, сдвигаем на один бит num1 >>= 1 while num2 != 0: # пока число нечётное, сдвигаем на один бит while num2 & 1 == 0: num2 >>= 1 # если первое число больше второго if num1 > num2: # меняем их местами num1, num2 = num2, num1 #теперь первое число меньше второго, вычитаем num2 -= num1 # возвращаем число, перед этим сдвинув его биты на shift return num1 
Результат выполнения не будет отличаться от результатов, полученных другими реализациями.
Тест скорости выполнения
Для выполнения теста воспользуемся функцией monotonic модуля time. Подробнее про неё и про то, как засечь время выполнения программы описано здесь.
Мы будем делать проверку, используя функцию выше описанного бинарного алгоритма Евклида и описанную в самом начале функцию классического.
Код проверки следующий:
start = time.monotonic() for i in range(10000): binary_gcd(168024, 105023) result = time.monotonic() - start print("binary time : .3f>".format(result) + " seconds") start = time.monotonic() for i in range(10000): gcd_rem_division(168024, 105023) result = time.monotonic() - start print("standard time: .3f>".format(result) + " seconds")
 
Результат теста выглядит следующим образом:
 
binary time : 0.219 seconds standard time: 0.094 seconds
 
Из результатов видно, что реализация классического алгоритма на Python быстрее, чем бинарного. Так что лучше на Python использовать классический алгоритм Евклида, а если программировать на C++ и важна скорость выполнения, то тогда использовать бинарный.
 
Заключение
 
Алгоритм Евклида позволяет эффективно находить общие делители чисел. За много лет его существования было придумано несколько различных видов, которые могут отличаться по способу реализации и эффективности.
 
Любой вид алгоритма Евклида можно реализовать на языке Python без использования сторонних библиотек.
 
Источник
 
Алгоритм Евклида - нахождение наибольшего общего делителя
 
Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.
 
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.
 
Решение задачи на языке программирования Python
 
Алгоритм нахождения НОД делением
 
 
Большее число делим на меньшее.
 
Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
 
Если есть остаток, то большее число заменяем на остаток от деления.
 
Переходим к пункту 1.
 
 
Пример: 
Найти НОД для 30 и 18. 
30 / 18 = 1 (остаток 12) 
18 / 12 = 1 (остаток 6) 
12 / 6 = 2 (остаток 0) 
Конец: НОД – это делитель 6. 
НОД (30, 18) = 6
 
a = int(input()) b = int(input()) while a != 0 and b != 0: if a > b: a = a % b else: b = b % a print(a + b)
 
В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для определения НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.
 
Если условием завершения цикла является равенство хотя бы одной из переменных нулю ( a == 0 or b == 0 ), то условием продолжения его работы является обратное этому условие - обе переменные должны иметь отличные от нуля значения ( a != 0 and b != 0 ).
 
 
 
Для того, чтобы вышеприведенная программа могла обрабатывать отрицательные числа, в логическом выражении при if должны сравниваться модули значений переменных: if abs ( a ) > abs ( b ) : . Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.
 
Алгоритм нахождения НОД вычитанием
 
 
Из большего числа вычитаем меньшее.
 
Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла).
 
Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
 
Переходим к пункту 1.
 
 
Пример: 
Найти НОД для 30 и 18. 
30 - 18 = 12 
18 - 12 = 6 
12 - 6 = 6 
6 - 6 = 0 
Конец: НОД – это уменьшаемое или вычитаемое. 
НОД (30, 18) = 6
 
a = int(input()) b = int(input()) while a != b: if a > b: a = a - b else: b = b - a print(a)
 
Функция, вычисляющая НОД
 
def gcd(m, n): while m != n: if m > n: m = m - n else: n = n - m return n a = int(input()) b = int(input()) print(gcd(a, b))
 
Функция gcd модуля math
 
В модуле math языка программирования Python есть функция gcd , вычисляющая наибольший общий делитель двух чисел.
 
>>> import math >>> math.gcd(30, 18) 6
 
Источник