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



              

Расширенный алгоритм Евклида - часть 2


Это нетрудно сделать, исходя из инварианта цикла. В обычном алгоритме Евклида пара (a,b) заменяется на (b,r), где r - остаток от деления a на b.

a = gb+r, |r| < |b|.

Здесь g равняется целой части частного от деления a на b. Заметим, что в программировании, в отличие от школьной математики, операция взятия целой части перестановочна с операцией изменения знака:

целая часть(-x) = - целая часть(x)

Например, целая часть(-3.7) = -3. Это позволяет работать с отрицательными числами так же, как и с положительными, т.е. вообще не следить за знаком! Отметим также, что в большинстве языков программирования считается, что результат любой операции с целыми числами является целым числом, например, 8/3 = 2.

Переменная g вычисляется как целая часть частного от деления a на b:

g = целая часть (a/b)

Выразим остаток r в виде линейной комбинации a и b:

r = a-gb

Используя инвариант цикла, можно выразить r через исходные числа m и n:

r = a-gb = (u1m+v1n)-g(u2m+v2n) = = (u1-gu2)m+(v1-gv2)n.

Через u'1, v'1, u'2, v'2 обозначаются новые значения переменных u1, v1, u2, v2. При замене (a,b)

(b,r) они вычисляются следующим образом:

u'1 = u2, v'1 = v2

u'2 = u1-gu2, v'2 = v1-gv2

По завершению цикла ответ будет находиться в переменных a (НОД исходных чисел m и n), u1, v1 (коэффициенты выражения НОД через m и n).

Выпишем алгоритм:

алгоритм Расширенный алгоритм Евклида( вх: цел m, цел n, вых: цел d, цел u, цел v ) | дано: целые числа m, n, хотя бы одно отлично от нуля; | надо: вычислить d = НОД(m, n) и найти u, v такие, что | d = u * m + v * n; начало алгоритма | цел a, b, q, r, u1, v1, u2, v2; | цел t; // вспомогательная переменная | // инициализация | a := m; b := n; | u1 := 1; v1 := 0; | u2 := 0; v2 := 1; | утверждение: НОД(a, b) == НОД(m, n) и | a == u1 * m + v1 * n и | b == u2 * m + v2 * n; | | цикл пока b != 0 | | инвариант: НОД(a, b) == НОД(m, n) и | | a == u1 * m + v1 * n и | | b == u2 * m + v2 * n; | | q := a / b; // целая часть частного от деления a на b | | r := a % b; // остаток от деления a на b | | a := b; b := r; // заменяем пару (a, b) на (b, r) | | | | // Вычисляем новые значения переменных u1, u2 | | t := u2; // запоминаем старое значение u2 | | u2 := u1 - q * u2; // вычисляем новое значение u2 | | u1 := t; // новое значение u1 := старое | | // значение u2 | | // Аналогично находим новые значения переменных v1, v2 | | t := v2; | | v2 := v1 - q * v2; | | v1 := t; | конец цикла | | утверждение: b == 0 и | НОД(a, b) == НОД(m, n) и | a == u1 * m + v1 * n; | // Выдаем ответ | d := a; | u := u1; v := v1; конец алгоритма




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