Как найти нод пайтон

Курс по Python: https://stepik.org/course/100707

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

Но, вначале пару
слов о самом алгоритме Евклида, о принципе его работы. Сначала рассмотрим его
медленный, но простой вариант.

Например, пусть
даны два натуральных числа: a = 18 и b = 24. Чтобы
определить для них НОД, будем действовать, следующим образом. Из большего
значения вычтем меньшее и результат сохраним в переменной с большим значением,
то есть, в b. Фактически,
это означает, что мы выполняем операцию: b = b – a. Теперь у нас
два значения a = 18, b = 6. Для них
повторяем тот же самый процесс. Здесь большее уже переменная a, поэтому,
корректируем ее значение, вычитая меньшее. Получаем новую пару a = 12, b = 6. Опять
повторяем этот процесс и видим, что a = 6, b = 6 –
переменные равны. В этом случае останавливаем алгоритм и получаем, что НОД(18,
24) = 6, что, в общем то, верно.

Весь этот
алгоритм можно представить следующим псевдокодом:

Давайте его
опишем с помощью, следующей функции:

def get_nod(a, b):
    """Вычисляется НОД для натуральных чисел a и b
        по алгоритму Евклида.
        Возвращает вычисленный НОД.
    """
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
 
    return a

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

Выполним эту
функцию со значениями аргументов 18 и 24:

res = get_nod(18, 24)
print(res)

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

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

После того, как
функция определена, ее следует протестировать и убедиться в корректности
возвращаемых результатов. Для этого тестировщик создает свою вспомогательную
функцию. Используя наши текущие знания, мы ее опишем, следующим образом:

def test_nod(func):
    # -- тест №1 -------------------------------
    a = 28
    b = 35
    res = func(a, b)
    if res == 7:
        print("#test1 - ok")
    else:
        print("#test1 - fail")
 
    # -- тест №2 -------------------------------
    a = 100
    b = 1
    res = func(a, b)
    if res == 1:
        print("#test2 - ok")
    else:
        print("#test2 - fail")
 
    # -- тест №3 -------------------------------
    a = 2
    b = 10000000
 
    st = time.time()
    res = func(a, b)
    et = time.time()
    dt = et - st
    if res == 2 and dt < 1:
        print("#test3 - ok")
    else:
        print("#test3 - fail")

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

Далее, выполним
импорт нужного нам модуля time для вызова
функции time():

и в конце вызовем
тестирующую функцию для тестирования get_nod:

Смотрите, у нас
первые два теста прошли, а третий – не прошел, так как функция слишком долго
вычисляла результат.

Давайте поправим
ее и ускорим алгоритм Евклида. Как это можно сделать? Смотрите, если взять два
числа a = 2 и b = 100, то по
изначальному алгоритму мы будем делать многочисленные вычитания из b a, пока значения
не сравняются. То есть, мы здесь, фактически, вычисляем остаток от вхождения
двойки в сотню, а это есть не что иное, как операция:

b = b % a = 0

И никаких
циклических вычитаний! Это, очевидно, будет работать много быстрее. При этом,
как только получаем остаток равный нулю, то НОД – это значение меньшей
переменной, то есть, в нашем примере – a = 2.

То же самое для
предыдущих значений a = 18, b = 24. Получаем серию таких
вычислений:

b = 24 % 18 = 6

a = 18 % 6 = 0

Значит, НОД(18,
24) = 6. Видите, как это быстро и просто! На уровне псевдокода быстрый алгоритм
Евклида можно описать так:

пока
меньшее число больше 0

        
большему числу присваиваем остаток от деления на меньшее число

выводим большее
число

Реализуем его в
виде функции:

def get_fast_nod(a, b):
    """Вычисляется НОД для натуральных чисел a и b
        по быстрому алгоритму Евклида.
        Возвращает вычисленный НОД.
    """
    if a < b:
        a, b = b, a
 
    while b != 0:
        a, b = b, a % b
 
    return a

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

Как видите, она
проходит все три наших теста.

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

Курс по Python: https://stepik.org/course/100707

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

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

• 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.

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

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

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

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

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

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

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

• g – Greatest (наибольший);
• c – Common (общий);
• d – Divisor (делитель).

Реализация на 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'Делитель равен {a[0]}, x = {a[1]}, y = {a[2]}')

Делитель равен 2, x = 69, y = -88

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

69*426-334*88 = 2

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

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

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

• x = y — (num2 // num1) * x
• y = x

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

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

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

Сложность алгоритма по прежнему определяется функций O(h²), однако реальные тесты показывают, что бинарный алгоритм эффективнее классического на 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 << shift

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

Тест скорости выполнения

Для выполнения теста воспользуемся функцией 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 без использования сторонних библиотек.