Алгоритмы неформально. Инструкция для начинающих питонистов - [12]

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

Как и многие лучшие алгоритмы, RPM также подчеркивает отношения между разрозненными, на первый взгляд, идеями. Может показаться, что двоичное разложение представляет интерес только для создателей транзисторов, но бесполезно для обывателя или профессионального программиста. Однако RPM демонстрирует глубокую связь между двоичным разложением числа и удобным способом умножения, требующим минимальных знаний таблицы умножения. Это еще одна причина, по которой всегда следует продолжать учиться: никогда не знаешь, когда бесполезный, на первый взгляд, факт может оказаться основой для мощного алгоритма.

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

Древние греки преподнесли человечеству много даров. Одним из самых выдающихся их изобретений стала теоретическая геометрия, которая была методично собрана великим Евклидом в серию из 13 книг, названную «Начала». Большая часть математических трудов Евклида написана в стиле «теорема/доказательство», при котором сложное предположение логически выводится из более простых. Некоторые из его работ также были конструктивными, то есть в них предоставлялся метод использования простых средств для построения полезных фигур или линий — например, квадрата с заданной площадью или касательной к кривой. И хотя сам термин «алгоритм» в то время еще не был придуман, конструктивные методы Евклида были алгоритмами, а некоторые из идей, лежащих в основе этих алгоритмов, актуальны и в наши дни.

Алгоритм Евклида вручную

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

Дано два натуральных (целых) числа: назовем их a и b. Допустим, a больше b (а если нет, то просто переименуйте a в b, а b в a, и тогда a будет большим). Если разделить a / b, то вы получите целое частное и целый остаток. Обозначим частное q1, а остаток c. Это можно записать так:

a = q1×b + c.

Например, если a = 105 и b = 33, то результат 105 / 33 равен 3, а остаток 6. Обратите внимание: остаток c всегда меньше как a, так и b — по определению остатка. На следующем шаге процесса мы забываем об a и концентрируемся на b и c. Как и прежде, допустим, что b больше c. Далее вычисляется частное и остаток при делении b / c. Обозначаем частное q2, а остаток d, и записываем результат:

b = q2×c + d.

И снова d будет меньше b и c, так как это остаток. Присмотревшись к двум уравнениям, можно заметить закономерность: мы продвигаемся по алфавиту, каждый раз сдвигая слагаемые влево. Мы начинали с a, b и c и перешли к b, c и d. Эта закономерность продолжается и на следующем шаге, на котором вычисляется результат c / d с получением частного q3 и остатка e.

c = q3×d + e.

Процесс продолжается, пока остаток не окажется равным нулю. Помните, что остатки всегда меньше чисел, которые делились для их получения: c меньше a и b, d меньше b и c, e меньше c и d, и т.д. Это означает, что на каждом шаге мы работаем со все меньшими числами, поэтому со временем доберемся до нуля. При получении нулевого остатка процесс останавливается, и мы знаем, что последний ненулевой остаток является наибольшим общим делителем. Например, если окажется, что e равно нулю, то d является наибольшим общим делителем двух исходных чисел.

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

Алгоритм Евклида достаточно легко реализуется на Python (листинг 2.1).

Листинг 2.1. Рекурсивная реализация алгоритма на языке Python

def gcd(x,y):

    larger = max(x,y)

    smaller = min(x,y)

    remainder = larger % smaller

    if(remainder == 0):

        return(smaller)

    if(remainder != 0):

❶        return(gcd(smaller,remainder))

Первое, на что следует обратить внимание, — что частные q1, q2, q3... не нужны. Достаточно остатков, представленных буквами алфавита. Узнать остаток в Python несложно: это делается с помощью оператора %, который упоминался выше. Можно написать функцию, вычисляющую остаток от деления двух чисел. Если остаток равен 0, то наибольшим общим делителем является меньшее из двух входных значений. Если остаток отличен от нуля, то меньшее из двух входных значений и остаток становятся входными значениями для той же функции.

Обратите внимание: эта функция вызывает сама себя, если остаток отличен от нуля ❶. Механизм вызова функцией самой себя называется рекурсией. На первый взгляд, рекурсия кажется чем-то непонятным и устрашающим; такой вызов представляется неким парадоксом, наподобие змеи, которая пытается проглотить саму себя, или попыток барона Мюнхгаузена вытянуть себя за волосы из болота. Не бойтесь! Если вы еще не знакомы с рекурсией, то лучше всего начать с конкретного примера: скажем, определить наибольший общий делитель 105 и 33 и выполнить каждый этап кода так, как если бы вы были компьютером. Этот пример покажет, что рекурсия является всего лишь компактным способом выражения действий, описанных в подразделе «Алгоритм Евклида вручную» на с. 48. При рекурсии всегда существует опасность создания бесконечной рекурсии — то есть функция вызывает сама себя, в процессе вызова снова вызывает сама себя и т.д. Ничто не заставляет функцию завершиться, поэтому она пытается вызывать сама себя бесконечно — а это создает проблему, поскольку программа должна завершиться, чтобы мы получили результат. В данном случае все выглядит безопасно, так как на каждом шаге мы получаем все меньшие остатки, которые в итоге уменьшатся до нуля, что позволит выйти из функции.