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. При рекурсии всегда существует опасность создания бесконечной рекурсии — то есть функция вызывает сама себя, в процессе вызова снова вызывает сама себя и т.д. Ничто не заставляет функцию завершиться, поэтому она пытается вызывать сама себя бесконечно — а это создает проблему, поскольку программа должна завершиться, чтобы мы получили результат. В данном случае все выглядит безопасно, так как на каждом шаге мы получаем все меньшие остатки, которые в итоге уменьшатся до нуля, что позволит выйти из функции.
Алгоритм Евклида компактен, элегантен и полезен. Предлагаю вам подумать над тем, как создать еще более компактную реализацию этого алгоритма на Python.
Японские магические квадраты
История японской математики особенно увлекательна. В книге «История японской математики», опубликованной в 1914 году, историки Дэвид Юджин Смит (David Eugene Smith) и Ёсио Миками (Yoshio Mikami) написали, что японская математика исторически обладала «гениальной способностью прикладывать титанические усилия» и «изобретательностью в распутывании тысяч мелких узелков». С одной стороны, математики открывают абсолютные истины, которые не должны зависеть от времени и культуры. С другой — те или иные группы обычно склонны концентрироваться на задачах определенного типа и создают свои специфические подходы к ним, не говоря уже о различиях в системах записи и обмена информацией. И этот факт позволяет оценить примечательные культурные различия даже в такой аскетичной области, как математика.
