ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 76211
УсловиеДаны натуральные 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-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |
Проект осуществляется при поддержке