Сложение многочлена Р с многочленом Q
осуществляется
следующим образом.
Граничное условие:
Р, складываемый с [], дает Р.
[], складываемый с Q, дает Q.
Рекурсивное условие:
При сложении Р с Q, в результате чего получается многочлен R,
возможны 4 случая:
1. Степень первого терма в Р меньше, чем степень первого терма в Q. В
этом случае первый терм многочлена Р образует первый терм в R, а
хвост R получается при прибавлении хвоста Р к Q. Например, если Р и
Q имеют вид
Р(х)=3х^2+5х^3
Q(x)=4x^3+3x^4
то первый терм
R(x)
равен
3х^2
(первому терму в
Р(х)
). Хвост
R(x)
равен
9х^3+3х^4
, т.е. результату сложения
Q(x)
и хвоста
Р(х)
;
2. Степень первого терма в Р больше степени первого терма в Q. В
данном случае первый терм в Q образует первый терм в R, а хвост R
получается при прибавлении Р к хвосту Q. Например, если
Р(х)=2х^3+5х^'4
Q(x)=3x^3-x^4
то первый терм
R(x)
равен
3х^2
(первому терму в
Q(x)
), а хвост
R(x)
равен
2х^3+4х^4
(результату сложения
Р(х)
и хвоста
Q(x)
);
3. Степени первых термов в Р и Q равны, а сумма их коэффициентов
отлична от нуля. В таком случае первый терм в R имеет коэффициент,
равный сумме коэффициентов первых термов в Р и Q. Степень первого
137
терма в R равна степени первого терма в Р (или Q). Хвост R получается
при сложении хвоста Р и хвоста Q. Например, если Р и Q имеют вид
Р(х)=2х+3х^3
Q(x)=3x+4x^4
то первый терм многочлена
R(х)
равен
5х
(результату сложения
первого терма в
Р(х)
с первым термом в
Q(x)
). Хвост
R(x)
равен
3х^3+4х^4
(результату сложения хвоста
Р(х)
и хвоста
Q(x)
);
4. Степени первых термов в Р и Q одинаковы, но сумма коэффициентов
равна нулю. В данном случае многочлен R равен результату сложения
хвоста Р с хвостом Q. Например, если
р(х)=2+2х
Q(x)=2-3x^2
то
R(x)=2x-3x^2
(это результат сложения хвостов многочленов
Р(х)
и
Q(х)
).
Рассмотренный
процесс
сложения
многочленов
можно
непосредственно записать на языке Пролог.
/* Граничные условия
слож_мн([], Q Q).
слож_мн(P, [], P).
/* Рекурсивное условие
/* (a)
слож_мн([x(Pc, Pp)|Pt], [x(Qc, Qp)|Qt],
[x(Pc,Pp)IRt]) :-
PpQp,
слож_мн(Рt, [х(Qс,Qр)|Qt], Rt).
/*(б)
слож_мн([x(Pc, Pp)|Pt], [x(Qc, Qp)|Qt],
[x(Qc, Qp)|Rt]) :-
PpQp,
слож_мн([x(Pc, Pp)|Pt], Qt, Rt).
/*(в)
слож_мн([x(Pc, Pp)|Pt], [х(Qc,Pp)|Qt],
[x(Rc, Pp)|Rt]) :-
Rc is Pc+Qc,
Rc =\= 0,
138
слож_мн(Pt, Qt,Rt).
/*(r)
слож_мн([х(Рс, Рр)|Pt],
[x(Qc.Pp)|Qt], Rt) :-
Re is Pc+Qc,
Rc =:= 0,
слож_мн(Pt, Qt, Rt).
Заметим, что в двух последних утверждениях проверка на равенство
осуществляется следующим образом: степени первых термов складываемых
утверждений обозначает одна и та же переменная
Pp
.
Списки как термы. В начале лекции мы упомянули о том, что список
представляется с помощью терма. Такой терм имеет функтор '.', два
аргумента и определяется рекурсивно. Первый аргумент является головой
списка, а второй — термом, обозначающим хвост списка. Пустой список
обозначается
[]
. Тогда список
[а, b]
эквивалентен терму
.(а,.(b, []))
.
Таким образом, из списков, как и из термов, можно создавать
вложенные структуры. Поэтому выражение
[[a, b], [c, d], [a], a]
есть правильно записанный список, и на запрос:
?- [Н|Т]=[[а, b], с].
Пролог дает ответ:
Н=[а, b] Т=[с]
В основу главы 14 положен материал учебного курсу [7].
139
Do'stlaringiz bilan baham: |