Условие
Даны натуральные
a и
b, не равные
0
одновременно. Найти
d =
НОД(a,b) и такие
целые
x и
y, что
d =
a . x +
b . y.
Решение
Добавим в алгоритм Евклида переменные
p,
q,
r,
s и впишем в инвариант условия
m =
p*a+q*b;
n = r*a+s*b.
m:=a; n:=b; p := 1; q := 0; r := 0; s := 1;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0
m = p*a + q*b; n = r*a + s*b.}
while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n; p := p - r; q := q - s;
| end else begin
| | n := n - m; r := r - p; s := s - q;
| end;
end;
if m = 0 then begin
| k :=n; x := r; y := s;
end else begin
| k := m; x := p; y := q;
end;
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
1 |
|
Название |
Задачи без массивов |
|
задача |
|
Номер |
1.1.15 |
