Быстрый поиск

Дипломная работа: Алгоритмы с многочленами

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;

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;

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;

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;

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;

Edit6.Text:=s;

end;

end.

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

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

В общем же случае многочлены и могут обладать делителями, зависящими от , и введем понятие о наибольшем общем делителе этих многочленов.

Наибольшим общим делителем отличных от нуля многочленов и называется такой многочлен , который является их общим делителем и, вместе с тем, сам делится на любой другой общий делитель этих многочленов. Обозначается наибольший общий делитель многочленов и символом .

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

2.4. Алгоритм Евклида

Алгоритм Евклида – метод для нахождения наибольшего общего делителя двух целых чисел, а также двух многочленов от одного переменного. Он первоначально был изложен в «Началах» Евклида в геометрической форме как способ нахождения общей меры двух отрезков. Алгоритм Евклида для нахождения наибольшего общего делителя, как в кольце целых чисел, так и в кольце многочленов от одного переменного является частным случаем некого общего алгоритма в евклидовых кольцах.

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

Для доказательства запишем изложенное в виде следующей цепочки равенств:

(2.4)

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

Возьмем теперь произвольный общий делитель многочленов и . Так как левая часть и первое слагаемое правой части первого из равенств делятся на , то также будет делится на . Переходя ко второму и следующему равенствам, таким же способом получим, что на делятся многочлены , , … Наконец, если уже будет доказано, что и делятся на , то из предпоследнего равенства получим, что делится на . Таким образом, на самом деле будет наибольшим общим делителем для и .

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

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

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

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