Алгоритм Евклида для нахождения НОД

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

Смотреть материал на YouTube | RuTube

На этом занятии я хочу показать вам пример использования функций для решения одной частной задачи – нахождения наибольшего общего делителя (НОД) для двух натуральных чисел 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, что, в общем то, верно.

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

пока a != b
находим большее среди a и b
уменьшаем большее на величину меньшего

выводим полученное значение величины a (или b)

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

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. Вот пример правильного оформления ключевых функций программы. Мало того, встроенная функция:

help(get_nod)

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

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

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():

import time

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

test_nod(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

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

test_nod(get_fast_nod)

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

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

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

Алгоритм Евклида для нахождения НОД

Видео по теме