Арифметика многочленов

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Выбор структуры хранения полинома

При выполнении работы можно использовать следующее понимание полинома. Полином состоит из мономов. Каждый моном характеризуется коэффициентом Coef и степенями переменных A, B, C: Coef*x^Ay^Bz^C. Величину степеней переменных можно ограничить значением 9. При таком предположении максимально возможное количество мономов в полиноме - 1000. Полином разрежен, если по сравнению с максимально возможным количеством мономов он имеет относительно небольшое количество отличных от нуля коэффициентов. Например, у полинома P(x,y,z) отличных от нуля коэффициентов всего 4.

При манипуляции разреженными полиномами эффективной структурой хранения являются списки. При этом каждое звено списка хранит моном с отличным от нуля коэффициентом.

Структура хранения полиномов должна обеспечивать эффективное выполнение операций. Если мономы в списке упорядочить по степеням переменных, то можно предложить эффективный алгоритм сложения полиномов, основанный на идее алгоритма слияния двух упорядоченных массивов.

В результате операций (например, сложения) может быть получен полином, у которого нет отличных от нуля коэффициентов. Структура хранения такого нулевого полинома не должна отличаться от структуры хранения прочих полиномов.

Для эффективного использования оперативной памяти реализуем операцию сложения таким образом, чтобы результат операции был получен на месте одного из слагаемых. При этом неизбежны вставки и удаления звеньев в списке. Для унификации вставок и удалений звеньев в начало, середину и конец списка рекомендуется использовать кольцевые списки.

Таким образом, с учетом вышеизложенного, рекомендуется следующая структура хранения полиномов. Полиномы упорядочиваются по убыванию степеней мономов. Для определения старшинства мономов вводится следующее правило. Во-первых, фиксируется старшинство переменных. Будем считать, что x - самая старшая переменная, затем следует y, затем z. Для каждого монома определим его "свернутую степень" (индекс). Для монома x^Ay^Bz^C. индекс равен A*10²+B*10¹+C*10⁰ (по условию задачи A, B и C не выше 9). Старшим считается моном с большей свернутой степенью. Например, x³y старше xy⁷z⁶, так как 310 больше 176.

Полином представляется кольцевым списком. Каждое звено списка соответствует моному с ненулевым коэффициентом. Звено состоит из трех полей и включает поле для хранения коэффициента, поле для хранения свернутой степени и поле для хранения указателя на звено следующего по порядку монома. Следующим после последнего звена является

Структура хранения нулевого полинома

Примеры структур хранения полиномов

первое звено списка. Первым звеном списка является так называемое "головное " звено (голова списка), поле свернутой степени которого равно -1. Нулевой полином представляется только головой списка.

Структуры хранения полиномов P(x,y,z), Q(x,y,z) и их суммы показаны на рисунке.

1.2 Полиноминальная арифметика

Арифметические операции естественным образом применимы не только к числам, но и к различным математическим величинам. В этом разделе речь пойдет о полиномах, что представляет шаг вперед по сравнению с числами. Формально говоря, полином над S представляет собой выражение вида

(1)

где коэффициенты U1, ..., Un, U0 — элементы некоторой алгебраической системы S, а переменная х может рассматриваться как формальный символ без определенного значения. Будем полагать, что алгебраическая система S представляет собой коммутативное кольцо с единицей. Это означает, что S допускает операции сложения, вычитания и умножения, удовлетворяющие обычным свойствам: сложение и умножение являются ассоциативными и коммутативными бинарными операциями, определенными на S, причем умножение дистрибутивно по отношению к сложению. Существует также единичный элемент по сложению 0 и единичный элемент по умножению 1, такие, что а + 0 = а и а • 1 = а для всех а из S. Вычитание является обратной по отношению к сложению операцией, но о возможности деления как об операции, обратной по отношению к умножению, ничего не предполагается.

Полином рассматривается как идентичный полиному (1), хотя формально он отличается от него.

Мы говорим, что (1) является полиномом степени n со старшим коэффициентом Un, если Un <> 0; в этом случае запишем

deg(u)=n, L(u)=Un

Кроме того, по определению

deg(0) = -оо,

L(0) = 0,

где 0 означает нулевой полином, т.е. полином, все коэффициенты которого равны нулю. Мы говорим также, что U(х) — нормированный полином, если его старший коэффициент L(u) равен 1.

Арифметика полиномов состоит, в первую очередь, из сложения, вычитания и умножения; иногда к этим операциям добавляются другие, например, деление, возведение в степень, разложение на множители и поиск наибольшего общего делителя. Сложение, вычитание и умножение определяются естественным образом, как если бы переменная х была элементом S: мы складываем или вычитаем полиномы посредством сложения или вычитания коэффициентов при одинаковых степенях х. Умножение выполняется согласно правилу

Где

В последней формуле Ui и Vj рассматриваются как равные нулю при i > г и j > s соответственно.

Алгебраическая система S обычно представляет собой множество целых или рациональных чисел. Она может быть и множеством полиномов (с другими, отличными от х переменными); тогда (1) — полином от нескольких переменных. В частности, алгебраическая система S может состоять из целых чисел 0, 1, ..., m — 1 со сложением, вычитанием и умножением, выполняемыми по модулю m, этот важный случай называется полиномиальной арифметикой по модулю m. Особенно важна полиномиальная арифметика по модулю 2, когда каждый коэффициент равен 0 или 1.

Имеется сходство между полиномиальной арифметикой и арифметикой многократной точности, где основание счисления Ь заменено на х. Основное отличие состоит в том, что коэффициент U_k при х^k в полиномиальной арифметике, вообще говоря, никак не связан с соседними коэффициентами Uk±i, так что понятие "перенос" из одного места в другое в полиномиальной арифметике отсутствует. В действительности полиномиальная арифметика по модулю Ь, по существу, идентична арифметике с многократной точностью по основанию Ь за исключением отсутствия переносов. Например, сравним умножение (1101)2 на (1011)2 в двоичной системе счисления с аналогичным умножением х³ + х² + 1 на х³ + х + 1 по модулю 2.

Двоичные числа

1101 х 1011

1101

1101

1101

10001111

Полиномы по модулю 2

1101 х 1011

1101

1101

1101

1111111

Произведение этих полиномов по модулю 2 получено путем отказа от всех переносов и составляет х⁶ + х⁵ + х⁴ х³ + х² + х + 1. Если умножать полиномы так же, как целые числа, без получения остатков по модулю 2, результат будет равен х⁶ + х⁵ + х⁴ + Зх³ + х² + х + 1; переносы в данном случае также не используются, однако коэффициенты в произведении могут оказаться произвольно большими.

Необходимо отметить некоторые аспекты, отличающие практическое использование полиномиальной арифметики от арифметики многократной точности. Очень часто при работе с полиномами наблюдается тенденция к появлению большого количества нулевых коэффициентов и полиномов огромных степеней, а потому желательно использовать специальные формы представления полиномов. Кроме того, арифметика полиномов от нескольких переменных приводит к программам, которые легче всего понять в рамках рекурсии. Хотя методы сложения, вычитания и умножения полиномов сравнительно просты и понятны, несколько важных аспектов полиномиальной арифметики достойны специального рассмотрения. В следующих разделах будут обсуждаться деление полиномов и связанные с ним методы, такие как поиск наибольшего общего делителя и разложение на множители. Мы рассмотрим также проблему эффективного вычисления полиномов, т.е. задачу поиска значения u(х) при данном х принадлежащем S с использованием минимально возможного числа операций. Частный случай вычисления хⁿ при больших n достаточно важен и разбирается отдельно в разделе.

4.6.1. Деление полиномов

Разделить один полином на другой можно так же, как одно целое число с многократной точностью на другое, при выполнении арифметических операций с полиномами над полем. Поле S представляет собой коммутативное кольцо с единицей, в котором точное деление возможно так же, как и операции сложения, вычитания и умножения.. Как обычно, это означает, что для любых U,V принадлежащих S и V<>0 в S всегда имеется элемент w, такой, что u = vw. Наиболее важными полями коэффициентов, появляющимися в приложениях, являются

a) рациональные числа;

b) действительные или комплексные числа;

c) целые по модулю р, где р — простое число;

d) рациональные функции над полем, т. е. частное двух полиномов, коэффициенты которых находятся в этом поле, а знаменатель нормирован.

Особо важный случай представляет собой поле целых по модулю 2, в котором элементы могут принимать значения 0 и 1. Полиномы над этим полем (т. е. полиномы по модулю 2) имеют много общего с целыми числами в двоичной записи; рациональные функции над данным полем поразительно схожи с рациональными числами, числители и знаменатели которых представлены в двоичной записи.

Если даны два полинома, 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), легко увидеть, что u_n+k должно быть кратно v_n при переходе к шагу D2; отсюда будет найдено частное u(x)/v(x). Применяя это наблюдение рекурсивно, получим алгоритм, который отвечает на вопрос, является ли данный полином над S от любого числа переменных кратным другому полиному над S, а также алгоритм, который будет находить частное, если таковое существует.

Множество элементов области единственного разложения называется взаимно простым, если нет простого элемента этой области единственного разложения, который делит все остальные элементы. Полином над областью единственного разложения называется примитивным, если его коэффициенты взаимно просты (не путайте это понятие с совершенно другим понятием примитивных полиномов по модулю p.

2 ПРАКТИЧЕСКАЯ ЧАСТЬ

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.

2.1 Блок – схема алгоритма