Условие
(Э. Дейкстра) Добавим в алгоритм Евклида дополнительные
переменные
u,
v,
z:
m := a; n := b; u := b; v := a;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n; v := v + u;
| end else begin
| | n := n - m; u := u + v;
| end;
end;
if m = 0 then begin
| z:= v;
end else begin {n=0}
| z:= u;
end;
Доказать, что после исполнения алгоритма значение
z
равно удвоенному наименьшему общему кратному
чисел
a,
b:
z =
2 . НОК(
a, b).
Решение
Заметим, что величина
m . u +
n . v не меняется в ходе выполнения алгоритма.
Остаётся воспользоваться тем, что вначале она равна
2ab и что
НОД(
a,
b)
. НОК(
a,
b) =
ab.
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
1 |
|
Название |
Задачи без массивов |
|
задача |
|
Номер |
1.1.17 |
