Основы программирования



              

Алгоритм Евклида вычисления наибольшего общего делителя


Пусть даны два целых числа m и n, хотя бы одно из которых не равно нулю. Требуется найти их наибольший общий делитель. Напомним, что наибольшим общим делителем двух чисел m и n называется такой их общий делитель d, который делится на любые другие общие делители d'. Такое определение НОД подходит не только для чисел, но и для многочленов, поскольку в нем не используется сравнение по величине. Наибольший общий делитель определен с точностью до обратимого множителя; в частности, поскольку в кольце чисел обратимы только элементы ±1, НОД целых чисел определен с точностью до знака.

В качестве пространства X рассматривается множество пар целых чисел

X = {(a,b) | a, b

Z, a
0 или b
0}

Надо вычислить НОД для заданной пары чисел (m,n). В качестве инварианта используем утверждение, что НОД текущей пары чисел равен НОД исходной пары:

I(a,b): НОД(a,b) = НОД(m,n).

Следовательно, цикл надо строить таким образом, чтобы при изменении переменных a, b наибольший общий делитель пары (a,b) оставался неизменным. В качестве начальной точки x0 используется пара (m,n).

Обозначим через r остаток от деления a на b:

a = gb+r, где |r| < |b|.

Тогда нетрудно доказать, что НОД(b,r) = НОД(a,b). Достаточно показать, что множества общих делителей пары (b,r) и пары (a,b) совпадают. Пусть d делит b и r. Тогда из равенства a = gb+r вытекает, что d делит a. Обратно, пусть d делит a и b. Из определения остатка имеем:

r = a-gb.

Так как правая часть равенства делится на d, то r тоже делится на d.

Итак, при замене пары (a,b) на пару (b,r) НОД не меняется. Обозначим через T отображение

T:(a,b)

(b,r)

Условие I(a,b) является инвариантным для отображения T.

Осталось только определить условие завершения цикла Q(a,b). Выполнение этого условия должно обеспечивать решение задачи, т.е. нахождение HOД чисел a, b. Для какой пары чисел их НОД можно сразу вычислить? Проще всего, когда одно из чисел равно нулю. В этом случае

НОД(a,0) = a

Итак, в качестве условия завершения цикла используем условие, что вторая компонента пары (a, b) нулевая:




Содержание  Назад  Вперед