Алгоритмы с многочленами (стр. 3 из 9)
Я составила программу для нахождения частного и остатка.
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.
2.3. Наибольший общий делитель многочленов
Пусть даны произвольные многочлены
и 
. Многочлен будет называться общим делителем для и , если он служит делителем для каждого из этих многочленов. Свойство 5. показывает, что к числу общих делителей многочленов и принадлежат все многочлены нулевой степени. Если других общих делителей эти два многочлена не имеют, то они называются взаимно простыми.В общем же случае многочлены
и могут обладать делителями, зависящими от 
, и введем понятие о наибольшем общем делителе этих многочленов.Наибольшим общим делителем отличных от нуля многочленов
и называется такой многочлен 
, который является их общим делителем и, вместе с тем, сам делится на любой другой общий делитель этих многочленов. Обозначается наибольший общий делитель многочленов и символом 
.Это определение оставляет открытым вопрос, существует ли наибольший общий делитель для любых многочленов
и . Ответ на этот вопрос положительный. Существует метод для практического разыскания наибольшего общего делителя данных многочленов, называемый алгоритмом последовательного деления или алгоритмом Евклида. 2.4. Алгоритм Евклида
Алгоритм Евклида– метод для нахождения наибольшего общего делителя двух целых чисел, а также двух многочленов от одного переменного. Он первоначально был изложен в «Началах» Евклида в геометрической форме как способ нахождения общей меры двух отрезков. Алгоритм Евклида для нахождения наибольшего общего делителя, как в кольце целых чисел, так и в кольце многочленов от одного переменного является частным случаем некого общего алгоритма в евклидовых кольцах.
Алгоритм Евклида для нахождения наибольшего общего делителя двух многочленов
и состоит в последовательном делении с остатком на , затем на первый остаток 
,затем на второй остаток 
и так далее. Так как степени остатков все время понижаются, то в этой цепочке последовательных делений мы дойдем до такого места, на котором деление совершится нацело и процесс остановится. Последний отличный от нуля остаток 
, на который нацело делится предыдущий остаток 
, и является наибольшим общим делителем многочленов и .Для доказательства запишем изложенное в виде следующей цепочки равенств:
(2.4)
Последнее равенство показывает, что
служит делителем для . Отсюда следует, что оба слагаемых правой части предпоследнего равенства делятся на , а поэтому будет делителем и для 
. Далее, таким же путем, поднимаясь вверх, мы получим, что является делителем и для 
, …, 
, 
. Отсюда ввиду второго равенства, будет следовать, что служит делителем для , а поэтому, на основании первого равенства, - и для .Возьмем теперь произвольный общий делитель
многочленов и . Так как левая часть и первое слагаемое правой части первого из равенств делятся на , то также будет делится на . Переходя ко второму и следующему равенствам, таким же способом получим, что на делятся многочлены , 
, … Наконец, если уже будет доказано, что и делятся на 
, то из предпоследнего равенства получим, что делится на . Таким образом, на самом деле будет наибольшим общим делителем для и 
.