Компьютерная алгебра. Системы аналитических вычислений. Демьянович Ю.К. - 86 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

10) t:=residual(q/r)
{ вычисление остатка }
11) q:=r;
12) r:=t;
13) end;
14) exit (q); { выход: q}
15) end.
Нетрудно видеть, что фактически тот же алгоритм справедлив
для вычисления НОД многочленов q и r, если операцию abs взятия
абсолютной величины заменить операцией deg вычисления степени
многочлена.
С другой стороны, рассматриваемый алгоритм позволяет опре-
делить представление НОД в виде линейной комбинации исходных
данных. Для этого применим этот алгоритм с использованием ско-
бок [. . .] для обозначения пары значений, и с использованием Q и
R для представления текущих значений q и r в терминах началь-
ных данных. Получится так называемый "Расширенный алгоритм
Евклида".
1) begin
2) if abs(q) < abs(r) then
3) begin
4) t:=q;
5) q:=r;
6) r:=t;
7) Q:=[0,1];
8) R:=[1,0];
9) end
10) else
11) begin
12) Q:=[1,0];
13) R:=[0,1];
14) end;
15) until r 6= 0 do
16) begin
17) t:=residual(q/r)
{ вычисление остатка }
18) T:=Q-quotient(q/r)R;
87

Страницы