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