Задача 76213

Темы:    [ Знакомство с циклами ] [ Задачи с целыми числами ] [ НОД и НОК. Алгоритм Евклида ]

Сложность: 2 Классы:

Условие

(Э. Дейкстра) Добавим в алгоритм Евклида дополнительные переменные 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