2.2. Деление многочленов с остатком

Для многочленов, как и для целых чисел, существует алгоритм деления с остатком.

Теорема о делении с остатком. Для любых двух многочленов f(x) и g(x) можно найти такие многочлены q(x) и r(x , что

f(x)=g(x)q(x)+r(x),

причем степень r(x) меньше степени g(x) или же r(x)=0. Многочлены q(x) и r(x), удовлетворяющие этому условию, определяются однозначно.

Если разности f(x)-r(x) и обе делятся на g(x), то их разность также делится на g(x). Если бы многочлен s(x) был ненулевым, то он имел бы степень меньшую, чем g(x), и не мог бы тогда делится на g(x). Следовательно, s(x)=0, так что .

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

Пример. Найти частный и остаток от деления на .

1. и

|

Частным от деления на является многочлен , остатком - .

2. и

¦

Частным от деления на является многочлен , остатком - .

Это правило в общем виде можно сформулировать так:

1) разделить старший член многочлена f(x) на старший член g(x) и записать результат «под длинной стороной угла»;

2)умножить g(x) на результат действия 1) и записать произведение под многочленом f(x);

3) вычесть из f(x) записанный под ним многочлен;

4) проверить имеет ли результат действия 3) степень меньшую, чем степень g(x); если да (или результат нулевой), то он является остатком, а под длинной стороной угла записано частное, если нет, то применить к этому результату действие 1), рассматривая его как многочлен f(x).

Я составила программу для нахождения частного и остатка.

unit Unit1;

interface

uses

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

Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

SGd1: TStringGrid;

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Edit5: TEdit;

Edit6: TEdit;

Button1: TButton;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

Label9: TLabel;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

i,n,m,step,j,f:integer;

d,l,s:string;

a,a2,b,b2,k:array[0..100] of integer;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

begin

n:=StrToInt(Edit1.Text);

m:=StrToInt(Edit2.Text);

for i:=n+1 downto 1 do begin

a[i]:=StrToInt(SGd1.Cells[n-(i-1),0]);

end;

for i:=m+1 downto 1 do begin

b[i]:=StrToInt(SGd1.Cells[m-(i-1),1]);

end;

s:=f1(x)=;

for i:=n+1 downto 1 do begin

if a[i]<>0 then begin if(a[i-1]<0)or(i=1) then begin

str(a[i],l);

str(i-1,d);

s:=s+l+x^+d;

end

else begin

str(a[i],l);

str(i-1,d);

s:=s+l+x^+d++;

end;

end;

end;

Edit3.Text:=s;

s:=f2(x)=;

for i:=m+1 downto 1 do begin

if b[i]<>0 then begin if(b[i-1]<0)or(i=1) then begin

str(b[i],l);

str(i-1,d);

s:=s+l+x^+d;

end

else begin

str(b[i],l);

str(i-1,d);

s:=s+l+x^+d++;

end;

end;

end;

Edit4.Text:=s;

for j:=N+1 downto 1 do begin

a2[j]:=a[j];

b2[j]:=0;

end;

step:=n-m;

f:=n+2;

for i:=step+1 downto 1do begin

f:=f-1;

k[i]:=a2[f];

for j:=m+1 downto 1do begin

b2[j]:=k[i]*b[j];

end;

for j:=f downto 1 do begin

a2[j]:=a2[j]*b[m+1];

end;

for j:=f downto 1 do begin

a2[j]:=a2[j]-b2[j+1-i];

b2[j]:=0;

end;

end;

s:=h(x)=;

for i:=f downto 1 do begin

if k[i]<>0 then begin if(k[i-1]<0)or(i=1) then begin

str(k[i],l);

str(i-1,d);

s:=s+l+x^+d;

end

else begin

str(k[i],l);

str(i-1,d);

s:=s+l+x^+d++;

end;

end;

end;

Edit5.Text:=s;

s:=r(x)=;

for i:=n downto 0 do begin

if a2[i]<>0 then begin if(a2[i-1]<0)or(i=1) then begin

str(a2[i],l);

str(i-1,d);

s:=s+l+x^+d;

end

else begin

str(a2[i],l);

str(i-1,d);

s:=s+l+x^+d++;

end;

end;

end;

Edit6.Text:=s;

end;

end.