Смекни!
smekni.com

Алгоритмы с многочленами (стр. 4 из 9)

Мы доказали, что любые два многочлена обладают наибольшим общим делителем, и получили способ его вычисления. Этот способ показывает, что если многочлены

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

Если

есть наибольший общий делитель многочленов
и
, то, как показывают свойства 8. и 9., в качестве наибольшего общего делителя этих многочленов можно было бы выбрать также многочлен
, где
- произвольное число, отличное от нуля. Иными словами, их наибольший общий делитель двух многочленов определен лишь с точностью до множителя нулевой степени. Ввиду этого можно условиться, что старший коэффициент наибольшего общего делителя двух многочленов будет всегда считаться равным единице. Используя это условие можно сказать, что два многочлена тогда и только тогда взаимно просты, если их наибольший общий делитель равен единице. В самом деле, в качестве наибольшего общего делителя двух взаимно простых многочленов можно взять любое число, отличное от нуля, но, умножая его на обратный элемент, получим единицу.

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

Пример. Найти наибольший общий делитель многочленов

и
.

1.

и

Совершим требуемые деления с остатком:

|

|

|

Построение последовательности Евклида закончено. Ее последний член

есть наибольший общий делитель исходных многочленов.

2.

и

Совершим требуемые деления с остатком:

‌‌‌‌‌‌‌‌‌ ||

Построение последовательности Евклида закончено. Ее последний член

есть наибольший общий делитель исходных многочленов.

Я составила программу для нахождения наибольшего общего делителя двух многочленов:

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Edit1: TEdit;

Edit2: TEdit;

SGd1: TStringGrid;

Label3: TLabel;

Button1: TButton;

Label4: TLabel;

Edit4: TEdit;

Label5: TLabel;

Label6: TLabel;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

st1,st2:integer;

kof1,kof2,k1,k2:array[0..10] of integer;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var i,j,k_1,st3,l:integer;

sokr:boolean;

k2_2,k1_1:array[0..10] of integer;

begin

st1:=StrToInt(Edit1.Text);

st2:=StrToInt(Edit2.Text);

for i:=0 to st1 do begin

kof1[i]:=StrToInt(SGd1.Cells[i,0]);

k1[i]:=StrToInt(SGd1.Cells[i,0]);

end;

for i:=0 to st2 do begin

kof2[i]:=StrToInt(SGd1.Cells[i,1]);

k2[i]:=StrToInt(SGd1.Cells[i,1]);

end;

while kof2[0]<>0 do begin

repeat

Edit4.Text:='';

k_1:=k1[0];

if k1[0]<>kof2[0] then begin

if (k1[0] mod kof2[0])=0 then begin

for j:=0 to st2 do

k2[j]:=(k1[0] div kof2[0])*kof2[j];

end

else begin

if k2[0]<>1 then

for j:=0 to st1 do

k1[j]:=kof2[0]*k1[j];

if k_1<>1 then begin

for j:=0 to st2 do

k2[j]:=k_1*kof2[j];

end;

end;

end;

for i:=1 to st1 do begin

k1[i-1]:=k1[i]-k2[i];

end;

st1:=st1-1;

until st1<st2;

if k1[0]<>0 then begin //Сокращение

sokr:=true;

for i:=1 to st1 do

if k1[i]<>0 then begin

if (k1[i] mod k1[0])<>0 then sokr:=false;

end;

k_1:=k1[0];

if sokr=true then

for i:=0 to st1 do

k1[i]:=k1[i] div k_1;

end;

for i:=0 to st2 do //Заменамногочленов

k2_2[i]:=kof2[i];

for i:=0 to st1 do

k1_1[i]:=k1[i];

for i:=0 to 10 do begin

kof1[i]:=0;

k1[i]:=0;

kof2[i]:=0;

k2[i]:=0;

end;

for i:=0 to st2 do begin

k1[i]:=k2_2[i];

if k1[i]<>0 then

Edit4.Text:=Edit4.Text+IntToStr(k1[i])+'x^'+IntToStr(st2-i);

if (k2_2[i+1]>0)and(i<st2) then Edit4.Text:=Edit4.Text+'+';

end;

for i:=0 to st1 do begin

k2[i]:=k1_1[i];

kof2[i]:=k1_1[i];

end;

st3:=st1;

st1:=st2;

st2:=st3;

end;

end;

end.

Используем алгоритм Евклида для доказательства следующей теоремы:

Теорема. Если

есть наибольший общий делитель многочленов
и
, то можно найти такие многочлены
и
, что