"Прадедушка" всех алгоритмов

В книге “Начала” древнегреческого математика Евклида, написанной около 300 г. до н.э. (об этой книге и ее авторе см. отдельную статью в данном выпуске), приведен алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. Этот алгоритм — первый нетривиальный алгоритм, доживший до наших дней. Эту честь могли бы, пожалуй, оспаривать вавилонские методы решения некоторых систем квадратных уравнений с двумя неизвестными, появившиеся за полтора тысячелетия до Евклида. Однако они не выдерживают сравнения с алгоритмом Евклида, поскольку в них не содержится итераций и поскольку они были вытеснены современными алгебраическими методами.

Суть алгоритма Евклида нахождения НОД в следующем. Пусть f и g — одновременно не равные нулю целые неотрицательные числа, и пусть f g. Тогда, если g = 0, то НОД (f, g) = f, а если g 0, то для чисел f, g и r, где r — остаток от деления f на g, выполняется равенство НОД (f, g) = НОД(g, r).

Применение алгоритма Евклида к числам f и g состоит в выполнении друг за другом серии однотипных шагов, которые можно оформить в виде:

1. Проверка условия g = 0

если оно истинно

то

Присваивание значения f искомой

величине НОД

Переход к шагу 6.

все

2. Вычисление остатка r от деления f на g.

3. Присваивание значения g числу f.

4. Присваивание значения r числу g.

5. Переход к шагу 1.

6. Конец.

Так, при вычислении НОД (39,15) переходим от одной пары чисел к другой в следующей последовательности: (39, 15), (15, 9), (9, 6), (6, 3), (3, 0). Получаем, что НОД (39, 15) = 3.

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

На школьном алгоритмическом языке программа, реализующая алгоритм Евклида, может быть записана следующим образом:

алг Определение_НОД_двух_неотрицательных_чисел

нач цел f, g, r, НОД

|Ввод исходных чисел

вывод, нс, "Введите большее из двух чисел"

ввод f

вывод, нс, "Введите меньшее из двух чисел"

ввод g

|Определение НОД по алгоритму Евклида

нц пока g <> 0

r = mod(f, g)

f = g

g = r

кц

НОД = f

|Вывод результата

вывод нс, "Наибольший общий делитель

этих чисел равен", НОД

кон

Большинство древних алгоритмов со временем вытеснялось из вычислительной практики более новыми алгоритмами. Алгоритм Евклида избежал этой участи, только используемое Евклидом вычитание заменилось на операцию нахождения остатка от деления. Значение HОД(f, g) можно вычислить многими способами, например, с помощью следующего тривиального алгоритма: если g = 0, то взять в качестве НОД(f, g) значение f, иначе выбрать из чисел g, g – 1, ... 1 первое, при делении на которое f и g дают нулевые остатки. Но, как и другие подобные алгоритмы, последний алгоритм слишком разорителен. Например, в случае, когда f и g — взаимно простые числа¹, он требует 2g делений. В то же время, число делений, требуемое алгоритмом Евклида, не превосходит 2[log₂g] + 2 [1].

Задания для самостоятельной работы

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

1) на основе алгоритма Евклида;

2) на основе алгоритма, который в статье назван “тривиальным”.

2. Используя электронную таблицу Microsoft Excel, постройте графики зависимости числа делений, требуемых для расчета НОД двух взаимно простых чисел по алгоритму Евклида и по “тривиальному” алгоритму.

Результаты (можно по отдельным заданиям), пожалуйста, присылайте в редакцию.

Алгоритм Евклида допускает многочисленные обобщения. Прежде всего, как мы покажем ниже, вместе с НОД(f, g) можно вычислять целые и и v такие, что

fu + gv = НОД(f, g). (1)

Это дает возможность находить некоторое целочисленное решение произвольного уравнения вида

kx + ly = m, (2)

где k, l, m — целые числа такие, что k и l одновременно не равны 0, a m делится на d = HОД(| k |, | l |). Пусть| k |u + | l |v = d, тогда

| k |um/d + | l |vm/d = m

и, как следствие этого (учитывая знак абсолютной величины),

| k |(с₁um/d) + | l |(с₁vm/d) = m,

где с_j = , j = 1, 2.

Займемся алгоритмом нахождения целых чисел u и v, удовлетворяющих (1). Обозначим временно f через f₀, a g через f₁, получаемые по алгоритму Евклида ненулевые остатки — через f₂, f₃, …, f_n, а частные от деления f₀ на f₁, f₁ на f₂, …, f_{n – 1} на f_n — через a₁, a₂, …, a_n:

f₀ = a₁f₁+ f₂,

f₁ = a₂f₂+ f₃,

… (3)

f_{n – 2} = a_{n – 1}f _{n – 1} + f_n,

f_{n – 1} = a_nf_n,

и здесь НОД(f₀, f₁) = f_n.

Пусть на некотором этапе нахождения НОД для некоторого i ? n – 2 вместе с числами f_{i + 1}, f_{i + 2} известны соответствующие им множители p, q, s, t такие, что:

f₀p + f₁q = f_i, f₀s + f₁t = f_{i + 1}. (4)

Тогда, разделив f_i на f_{i + 1} и получив частное а_{i + 1} и остаток f_{i + 2}, мы можем вычислить множители, соответствующие f_{i + 2}: так как согласно (3) a_{i – 1}f _{i – 1} + f_i = f_{i – 2}, то, используя для f_i, f_{i + 1} выражения (4), мы получаем:

f₀(р – а_{i + 1}s) + f₁(q – а_{i + 1}t) = f_{i + 2}.

Таким образом, для решения задачи (2) надо применять к f и g алгоритм Евклида, рассматривая на каждом шаге его применения, кроме тех двух чисел, которые рассматривались прежде, еще и соответствующие этим числам множители p, q, s, t. На первом шаге в качестве множителей, соответствующих исходным числам f и g, берутся 1, 0 и 0, 1. Выполнив деление и получив частное а и некоторый остаток, надо, если остаток не равен 0, перед переходом к следующему шагу вычислить по формулам р – as и q – at множители, соответствующие полученному остатку. Последний ненулевой остаток и соответствующие ему множители u и v будут удовлетворять (2).

В процессе применения этого алгоритма к f = 39, g = 15 последовательно вычисляются остатки 9; 6; 3; 0 и соответствующие первым трем из них множители 1, –2; –1, 3; 2, –5. Таким образом, 39 · 2 + 15 · (–5) = 3 = НОД (39, 15).

Заметим, что алгоритм можно изменить так, что число требуемых им операций сократится почти в полтора раза: из двух чисел и и v достаточно вычислять вместе с НОД(f, g) только v, а затем определить и по формуле и = (НОД(f, g) – gv)/f. Для f = 39, g = 15 мы могли бы положить и = (3 – 15 · (–5))/39 = 2.

В любом случае важно, что это метод решения одного уравнения с двумя неизвестными!

Задания для самостоятельной работы

Разработайте программу решения целочисленных уравнений вида (2):

1) на основе алгоритма, рассмотренного в статье;

2) на основе алгоритма, описанного в только что приведенном замечании.

Программы (можно по отдельным заданиям) также присылайте в редакцию. Все приславшие хотя бы одну правильную программу будут награждены дипломами.

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

Литература

1. Абрамов С.А. Самый знаменитый алгоритм. / “Квант”, № 11/1985.

---

¹ Взаимно простыми называют числа, наибольший общий делитель которых равен 1, но в общем случае при нахождении НОД это, естественно, заранее неизвестно.