расширенный алгоритм Евклида
Вернемся к примеру с расширенным алгоритмом Евклида, подробно рассмотренному в разделе 1.5.2. Напомним, что наибольший общий делитель двух целых чисел выражается в виде их линейной комбинации с целыми коэффициентами. Пусть x и y - два целых числа, хотя бы одно из которых не равно нулю. Тогда их наибольший общий делитель d = НОД(x,y) выражается в виде
d = ux+vy,
где u и v - некоторые целые числа. Алгоритм вычисления чисел d, u, v по заданным x и y называется расширенным алгоритмом Евклида. Мы уже выписывали его на псевдокоде, используя схему построения цикла с помощью инварианта.
Оформим расширенный алгоритм Евклида в виде функции на Си. Назовем ее extGCD (от англ. Extended Greatest Common Divizor). У этой функции два входных аргумента x, y и три выходных аргумента d, u, v. В случае выходных аргументов надо передавать функции указатели на переменные. Итак, функция имеет следующий прототип:
void extGCD(int x, int y, int *d, int *u, int *v);
При вызове функция вычисляет наибольший общий делитель от двух переданных целых значений x и y и коэффициенты его представления через x и y. Ответ записывается по переданным адресам d, u, v.
Приведем полный текст программы. Функция main вводит исходные данные (числа x и y), вызывает функцию extGCD и печатает ответ. Функция extGCD использует схему построения цикла с помощью инварианта для реализации расширенного алгоритма Евклида.
#include <stdio.h> // Описания стандартного ввода-вывода
// Прототип функции extGCD (расш. алгоритм Евклида) void extGCD(int x, int y, int *d, int *u, int *v);
int main() { int x, y, d, u, v; printf("Введите два числа:\n"); scanf("%d%d", &x, &y); if (x == 0 && y == 0) { printf("Должно быть хотя бы одно ненулевое.\n"); return 1; // Вернуть код некорректного завершения }
// Вызываем раширенный алгоритм Евклида extGCD(x, y, &d, &u, &v);
// Печатаем ответ printf("НОД = %d, u = %d, v = %d\n", d, u, v);
return 0; // Вернуть код успешного завершения }
void extGCD( int x, int y, int *d, int *u, int *v) { int a, b, q, r, u1, v1, u2, v2; int t; // вспомогательная переменная
// инициализация a = x; b = y; u1 = 1; v1 = 0; u2 = 0; v2 = 1;
// утверждение: НОД(a, b) == НОД(x, y) && // a == u1 * x + v1 * y && // b == u2 * x + v2 * y;
while (b != 0) { // инвариант: НОД(a, b) == НОД(x, y) && // a == u1 * x + v1 * y && // b == u2 * x + v2 * y; 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; }
Пример работы программы:
Введите два числа: 187 51 НОД = 17, u = -1, v = 4
Здесь первая и третья строка напечатаны компьютером, вторая введена человеком.
