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