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

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)