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

Смотреть материал на видео

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

Но для начала теория самого алгоритма Евклида. В самом простом варианте он формулируется так. Пусть даны два натуральных числа a и b, для которых требуется найти НОД. Тогда делаем такие операции:

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

Реализуем этот алгоритм на Python. Для начала объявим вот такую пустую функцию:

def getNOD(a, b):
    """Вычисляется НОД для натуральных чисел a и b
        по алгоритму Евклида.
        Возвращает вычисленный НОД.
    """

И, далее, в ней запишем сам алгоритм Евклида:

    while a != b:
        if a>b: a -= b
        else: b -=a
 
    return a

Для проверки правильности ее работы выполним небольшое тестирование с помощью следующей функции:

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

Для ее работы подключим модуль time:

import time

И в конце вызовем этот тест:

testNOD()

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

Теперь запустим программу и увидим, что первые два теста прошли, а последний не прошел по времени – программа слишком долго находила НОД чисел:

100000000 и 2

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

4-2 = 2

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

100000000 % 2 = 0

Это значит, что большее число можно полностью составить из суммы двоек. Следовательно, они оба делятся на два нацело и их НОД равен 2. Хорошо, а если вместо 2 взять 3. В этом случае имеем:

100000000 % 3 = 1

и далее уже можно рассматривать два числа: 3 и 1. Причем, для них также можно выполнить такую же операцию:

3 % 1 = 1
1 % 1 = 0

Все, получили НОД, равный 1. И смотрите, здесь на каждой итерации большее число делится на меньшее. Поэтому быстрый алгоритм Евклида можно записать так:

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

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

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

Реализуем этот алгоритм в функции getNOD. И договоримся, что большее число будем хранить в a, меньшее – в b.

    if a < b:
        a,b = b,a
 
    while b:
        a,b = b, a%b
 
    return a

В этом алгоритме используется свойство:

a%b = c, c < b

то есть, остаток всегда будет меньше числа b. Значит, из двух чисел c и b большим будет b, а меньшим – c. Именно поэтому в программе записано такое множественное присваивание:

a,b = b, a%b

Мы здесь переменной a присваиваем значение b, а b становится равным остатку от деления. Это гарантируется, что a >= b.

Задания для самоподготовки

1. Реализовать последний вариант алгоритма Евклида с помощью рекурсивной функции.

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

arg1, arg2, …, argN

3. Реализовать универсальную функцию для нахождения максимального или минимального значения среди аргументов:

arg1, arg2, …, argN

с помощью функции-селектора, указанной в виде лямбда-функции как один параметров функции поиска.

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

Задания для самоподготовки

Видео по теме