Рассмотрим пример использования списков решения задач на примере представления и сложения многочленов.
Представление многочленов. Посмотрим, как можно представить многочлен вида
Р(х)=3+3х-4х^3+2х^9
Q(х)=4х+х^2-3х^3+7х^4+8х^5
Заметим, что каждое подвыражение (такое, как Зх ^3, Зх, 3) имеет самое большее две переменные компоненты: число, стоящее перед х, называемое коэффициентом, и число, стоящее после ^ - степень. Следовательно, подвыражение представляется термом
х(Коэффициент, Степень)
Так, 5х^2 записывается как х(5,2), х^З представляется как х(1,3), а поскольку х^0 равно 1, подвыражению 5 соответствует терм х(5,0).
Теперь запишем многочлен в виде списка. Приведенный выше многочлен Р(х), например, будет выглядеть следующим образом:
[x(3, 0), '+', x(3, l), '-', x(4, 3), '+', x(2, 9)]
Воспользуемся тем, что многочлен
3 + 3х - 4х^3 + 2х^9
допускает замену на эквивалентный
3 + 3х + (-4)х^3 + 2х^9 Тогда он выражается списком:
[х(3, 0), '+', х(3, 1), '+', х(-4, 3), '+', х(2, 9)]
В такой записи между термами всегда стоят знаки '+'. Следовательно, их можно опустить, и многочлен принимает окончательный вид:
[х(3, 0), х(3, 1), х(-4, 3), х(2, 9)]
Подразумевается, что между всеми термами списка стоят знаки '+'. Представлением многочлена Q(x) будет
[х(4, 1), х(1, 2), х(-3, 3), х(7, 4), х(8, 5)]
Сложение многочленов. Теперь напишем целевые утверждения для сложения двух многочленов. Сложение многочленов
3-2х^2+4х^3+6х^6
-1+3х^2-4х^3
в результате дает
2+х^2+6х^6
Аргументами целевого утверждения являются многочлены, представленные в виде списков. Ответ будет получен также в виде списка.
Сложение многочлена Р с многочленом Q осуществляется следующим образом:
Граничное условие:
Р, складываемый с [], дает Р.
[], складываемый с Q, дает Q.
Рекурсивное условие:
При сложении Р с Q, в результате чего получается многочлен R, возможны 4 случая:
а) степень первого терма в Р меньше, чем степень первого терма в 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) и хвоста Р(х);
б) степень первого терма в Р больше степени первого терма в 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));
в) степени первых термов в Р и Q равны, а сумма их коэффициентов отлична от нуля. В таком случае первый терм в R имеет коэффициент, равный сумме коэффициентов первых термов в Р и Q. Степень первого терма в 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));
г) степени первых термов в Р и 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,
слож_мн(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]
Т=[с] |
Главная
Каталог файлов
