Арифметика многочленов (стр. 2 из 3)
Если даны два полинома, u{х) и v(x), над полем и v(x) <> 0, можно разделить u(х) на v(х) и получить полином-частное q(x) и полином-остаток г(х), удовлетворяющие условиям
Легко увидеть, что существует не более одной пары полиномов (q(x),r(x)), удовлетворяющих этим соотношениям; в самом деле, если условиям при одних и тех же полиномах u(х) и v(x) удовлетворяют две пары — (q1(x),r1(x)) и (q2(x),r2(x)),— то q1(x)v{x) + r1(x) = q2(x)v(x) + r2(x), т. е. (q1(x) -q2(x))v{x) = r2(х) – r1(х). Теперь, если q1(x) - q2(x) <> 0, имеем deg((g1 - q2) • v) - deg(q1 - q2) + deg(u) >= deg(v) > deg(r2 — r1), т.е. получаем противоречие (так как из равенства (q1(x) - q2(x))v(x) = r2(х) — r1(х) следует deg((g1 — q2) * v) = deg(r1 — r2)). Значит, q1(x) - q2(x) = О и r1(х) = r2(х).
Чтобы определить q(x) и r(х), можно использовать алгоритм для деления чисел с многократной точностью, только без переносов.
Области единственного разложения на множители. Если мы ограничимся рассмотрением полиномов над полем, то не охватим полиномы над множеством целых чисел и полиномы от нескольких переменных. Поэтому будем рассматривать более общую ситуацию, когда алгебраическая система коэффициентов S представляет собой область единственного разложения на множители и не обязана быть полем. Это означает, что S — коммутативное кольцо с единицей и что
i) uv <> 0, если u и v — ненулевые элементы S;
ii) каждый ненулевой элемент u, принадлежащий S, либо обратим, либо имеет "единственное" представление в виде произведения простых р1, .. , Pt
u = p1...pt, t>l (2)
Обратимый элемент в данном случае представляет собой элемент, который имеет обратную величину, а именно—элемент и, такой, что uv = 1 для некоторого v принадлежащих S. Простой элемент — это не являющийся обратимым элемент р, такой, что уравнение р = qr истинно только тогда, когда либо q, либо r представляет собой обратимый элемент. Представление (2) единственно в том смысле, что если р1.. .pt = q1 . . qs, где все р и q просты, то s = t и имеется перестановка пх . пt множества {1,..., t}, такая, что р1 = a1qп1, pt = atqпi для некоторых обратимых а1, ..., at. Другими словами, разложение на простые множители единственно с точностью до порядка множителей и до умножения на обратимые.
Любое поле представляет собой область единственного разложения на множители, в которой каждый ненулевой элемент обратим и в которой не существует простых элементов. Целые числа образуют область единственного разложения, в которой обратимые элементы +1 и —1, а простые —±2, ±3, ±5, ±7, ±11 и т. д. Случай, когда S содержит все целые числа, принципиален, поскольку зачастую предпочтительнее работать с целыми коэффициентами, а не с произвольными рациональными.
Одним из ключевых фактов, связанных с полиномами, является то, что полиномы над областью единственного разложения образуют область единственного разложения. Полином, который является простым в этой области, обычно называется неприводимым. Многократно используя теорему о единственности разложения, можно доказать, что полиномы от нескольких переменных над множеством целых чисел или над любым полем с любым числом переменных могут быть единственным образом разложены на неприводимые полиномы. Например, полином от трех переменных 90x^3 — 120х^2у + l8x^2yz - 24xy^2z над целыми числами представляет собой произведение пяти неприводимых полиномов 2*3*х*(3х—4у)*(5х+yz). Тот же полином над рациональными числами является произведением трех неприводимых полиномов (6х) (3х — 4у) • (5х + yz). Это разложение может быть записано как х • (90x - 120у) • (х + (1/5)yz) и еще бесконечным числом способов, хотя разложение, по существу, единственно.
Как обычно, мы говорим, что u(х) кратен полиному v(x), a v(x) является делителем u(х), если u(х) = v(x)q(x) для некоторого полинома q(x). Если есть алгоритм, который определяет, является ли и кратным v для произвольных ненулевых элементов u и v некоторой области единственного разложения S, и позволяет определить w, если u = v * w, то алгоритм дает метод для выяснения, является ли u(х) кратным v(x) для произвольных ненулевых полиномов u(х) и v(x) над S. Если u(х) кратно v(x), легко увидеть, что un+k должно быть кратно vn при переходе к шагу D2; отсюда будет найдено частное u(x)/v(x). Применяя это наблюдение рекурсивно, получим алгоритм, который отвечает на вопрос, является ли данный полином над S от любого числа переменных кратным другому полиному над S, а также алгоритм, который будет находить частное, если таковое существует.
Множество элементов области единственного разложения называется взаимно простым, если нет простого элемента этой области единственного разложения, который делит все остальные элементы. Полином над областью единственного разложения называется примитивным, если его коэффициенты взаимно просты (не путайте это понятие с совершенно другим понятием примитивных полиномов по модулю p.
2.1 Текст программы
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, Menus;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Label1: TLabel;
Label2: TLabel;
StringGrid2: TStringGrid;
StringGrid3: TStringGrid;
Label3: TLabel;
Memo1: TMemo;
Button1: TButton;
Button2: TButton;
Button3: TButton;
Button4: TButton;
Button5: TButton;
Button6: TButton;
MainMenu1: TMainMenu;
N1: TMenuItem;
N2: TMenuItem;
N3: TMenuItem;
N4: TMenuItem;
N5: TMenuItem;
Label4: TLabel;
procedure FormCreate(Sender: TObject);
procedure N5Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
procedure Button6Click(Sender: TObject);
procedure N2Click(Sender: TObject);
procedure N3Click(Sender: TObject);
procedure N4Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const n=5;
type mas1=array [1..n] of integer;
type mas2=array [1..n,1..n]of integer;
type mas3=array [1..n*2] of integer;
type mas4=array [1..n*2,1..n*2] of integer;
var
Form1: TForm1;
x1,x2,y1,y2:mas1;
x1y1,x2y2:mas2;
s1,s2:string;
xr,yr:mas1;
xyr:mas2;
xr1,yr1:mas3;
xyr1:mas4;
implementation
{$R *.dfm}
procedure TForm1.FormCreate(Sender: TObject);
var i:integer;
begin
for i:=1 to n do
begin
stringgrid1.Cells[i-1,0]:=inttostr(i);
stringgrid2.Cells[i-1,0]:=inttostr(i);
stringgrid3.Cells[i,0]:=inttostr(i);
stringgrid3.Cells[0,i]:=inttostr(i);
end;
end;
procedure TForm1.N5Click(Sender: TObject);
begin
close;
end;
procedure TForm1.Button1Click(Sender: TObject);
var k,i:integer;
begin
randomize;
s1:='';
for i:=1 to n do
begin
k:=random(2);
if k=1 then x1[i]:=random(10)-4
else x1[i]:=0;
stringgrid1.Cells[i-1,1]:=inttostr(x1[i]);
end;
for i:=1 to n do
if x1[i]<>0 then s1:=s1+'+('+inttostr(x1[i])+'*x^'+inttostr(i)+')';
end;
procedure TForm1.Button2Click(Sender: TObject);
var k,i:integer;
begin
randomize;
s2:='';
for i:=1 to n do
begin
k:=random(2);
if k=1 then x2[i]:=random(10)-4
else x2[i]:=0;
stringgrid1.Cells[i-1,2]:=inttostr(x2[i]);
end;
for i:=1 to n do
if x2[i]<>0 then s2:=s2+'+('+inttostr(x2[i])+'*x^'+inttostr(i)+')';
end;
procedure TForm1.Button3Click(Sender: TObject);
var k,i:integer;
begin
randomize;
for i:=1 to n do
begin
k:=random(2);
if k=1 then y1[i]:=random(10)-4
else y1[i]:=0;
stringgrid2.Cells[i-1,1]:=inttostr(y1[i]);
end;
for i:=1 to n do
if y1[i]<>0 then s1:=s1+'+('+inttostr(y1[i])+'*y^'+inttostr(i)+')';
end;
procedure TForm1.Button4Click(Sender: TObject);
var k,i:integer;
begin
randomize;
for i:=1 to n do
begin
k:=random(2);
if k=1 then y2[i]:=random(10)-4
else y2[i]:=0;
stringgrid2.Cells[i-1,2]:=inttostr(y2[i]);
end;
for i:=1 to n do
if y2[i]<>0 then s2:=s2+'+('+inttostr(y2[i])+'*y^'+inttostr(i)+')';
end;
procedure TForm1.Button5Click(Sender: TObject);
var k,i,j:integer;
begin
memo1.Lines.Add('Первый многочлен');
randomize;
for i:=1 to n do
for j:=1 to n do
begin
k:=random(2);
if k=1 then x1y1[i,j]:=random(10)-4
else x1y1[i,j]:=0;
stringgrid3.Cells[i,j]:=inttostr(x1y1[i,j]);
end;
for i:=1 to n do
for j:=1 to n do
if x1y1[i,j]<>0 then s1:=s1+'+('+inttostr(x1y1[i,j])+'*x^'+inttostr(i)+'y^'+inttostr(j)+')';
memo1.Lines.Add(s1);
end;
procedure TForm1.Button6Click(Sender: TObject);
var k,i,j:integer;
begin
memo1.Lines.Add('Второй многочлен');
randomize;
for i:=1 to n do
for j:=1 to n do
begin
k:=random(2);
if k=1 then x2y2[i,j]:=random(10)-4
else x2y2[i,j]:=0;
stringgrid3.Cells[i,j]:=inttostr(x2y2[i,j]);
end;
for i:=1 to n do
for j:=1 to n do
if x2y2[i,j]<>0 then s2:=s2+'+('+inttostr(x2y2[i,j])+'*x^'+inttostr(i)+'y^'+inttostr(j)+')';
memo1.Lines.Add(s2);
end;
procedure TForm1.N2Click(Sender: TObject);
var i,j:integer;
begin
memo1.Lines.Add('Сложение');
s1:='';
for i:=1 to n do
begin
xr[i]:=x1[i]+x2[i];
yr[i]:=y1[i]+y2[i];
end;
for i:=1 to n do
for j:=1 to n do
xyr[i,j]:=x1y1[i,j]+x2y2[i,j];
for i:=1 to n do
if xr[i]<>0 then
s1:=s1+'+('+inttostr(xr[i])+'x^'+inttostr(i)+')';
for i:=1 to n do
if yr[i]<>0 then
s1:=s1+'+('+inttostr(yr[i])+'y^'+inttostr(i)+')';
for i:=1 to n do
for j:=1 to n do
if xyr[i,j]<>0 then
s1:=s1+'+('+inttostr(xyr[i,j])+'x^'+inttostr(i)+'y^'+inttostr(j)+')';
memo1.Lines.Add(s1);
end;
procedure TForm1.N3Click(Sender: TObject);
var i,j:integer;
begin
memo1.Lines.Add('Вычитание');
s1:='';
for i:=1 to n do
begin
xr[i]:=x1[i]-x2[i];
yr[i]:=y1[i]-y2[i];
end;
for i:=1 to n do
for j:=1 to n do
xyr[i,j]:=x1y1[i,j]-x2y2[i,j];
for i:=1 to n do
if xr[i]<>0 then
s1:=s1+'+('+inttostr(xr[i])+'x^'+inttostr(i)+')';
for i:=1 to n do
if yr[i]<>0 then
s1:=s1+'+('+inttostr(yr[i])+'y^'+inttostr(i)+')';
for i:=1 to n do
for j:=1 to n do
if xyr[i,j]<>0 then
s1:=s1+'+('+inttostr(xyr[i,j])+'x^'+inttostr(i)+'y^'+inttostr(j)+')';
memo1.Lines.Add(s1);
end;
procedure TForm1.N4Click(Sender: TObject);
var i,j:integer;
begin
memo1.Lines.Add('Умножение');
s1:='';
for i:=1 to 2*n do
for j:=1 to 2*n do
begin
xr1[i]:=0;
yr1[i]:=0;
xyr1[i,j]:=0;
end;
for i:=1 to n do
for j:=1 to n do
begin
xr1[i+j]:=xr1[i+j]+x1[i]*x2[j];
yr1[i+j]:=yr1[i+j]+y1[i]*y2[j];
xyr1[i,j]:=xyr1[i,j]+x1[i]*y2[j];
xyr1[j,i]:=xyr1[j,i]+y1[i]*x2[j];
//xyr1[i,j]:=xyr1[i,j]+y1[i]*x2[j];
xyr1[i,j+j]:=xyr1[i,j+j]+x1y1[i,j]*y2[j];
xyr1[i+j,j]:=xyr1[i+j,j]+x1y1[i,j]*x2[j];
xyr1[i+i,j]:=xyr1[i+i,j]+x2y2[i,j]*x1[i];
xyr1[i,j+i]:=xyr1[i,j+i]+x2y2[i,j]*y1[i];
xyr1[i+i,j+j]:=xyr1[i+i,j+j]+x1y1[i,j]*x2y2[i,j];
end;
for i:=1 to 2*n do
if xr1[i]<>0 then
s1:=s1+'+('+inttostr(xr1[i])+'x^'+inttostr(i)+')';
for i:=1 to 2*n do
if yr1[i]<>0 then
s1:=s1+'+('+inttostr(yr1[i])+'y^'+inttostr(i)+')';
for i:=1 to 2*n do
for j:=1 to 2*n do
if xyr1[i,j]<>0 then
s1:=s1+'+('+inttostr(xyr1[i,j])+'x^'+inttostr(i)+'y^'+inttostr(j)+')';
memo1.Lines.Add(s1);
end;
end.
