Лабораторная работа №4 - Предикаты для работы со списками - файл n1.docx

Лабораторная работа №4 - Предикаты для работы со списками
скачать (27.3 kb.)
Доступные файлы (1):
n1.docx28kb.29.05.2012 23:35скачать

n1.docx

Рекурсивно-логическое программирование

лабораторная работа №4

Задание.

Запрограммировать на языке Пролог указанные ниже предикаты. Продемонстрировать различные варианты их использования на примерах.

В отчёте по лабораторной работе продемонстрировать для каждого предиката дать декларативную интерпретацию.


  1. div(X,Y,Z): Z – результат целочисленного деления X на Y, где X и Y – натуральные числа, представленные в структурированной форме (например, div(s(s(s(s(s(0))))),s(s(0)),s(s(0))) );

  2. gcd(X,Y,Gcd): Gcd – наибольший общий делитель натуральных чисел X и Y; процедура должна быть реализована без использования операции деления по модулю; при реализации можно использовать по желанию либо структурированное представление, либо обычное представление натуральных чисел.

  3. adjacent(X,Y,Zs): X и Y являются соседними элементами в списке Zs; процедура должна быть рекурсивной и не использовать предикат append/3;

  4. last(X,Xs): X является последним элементом списка Xs; процедура должна быть рекурсивной и не использовать предикат append/3;

  5. double(Xs,XsXs): XsXs – это список Xs, в котором каждый элемент повторён дважды (например, double([1,1,5,3,5],[1,1,1,1,5,5,3,3,5,5]) );

  6. sum(Ns,Sum): Sum – сумма элементов списка натуральных чисел Ns; при реализации использовать структурированное представление натуральных чисел и не использовать вспомогательные предикаты;

  7. substitute(X,Y,L1,L2): L2 – это список L1, в котором все вхождения элемента X заменены элементом Y.


Рекомендации.

1. Для реализации предикатов, работающих со структурированным представлением натуральных чисел необходимо предварительно описать предикаты nat_num/1, plus/3 и ll(X,Y). Последний из них истинен, если X<Y.

2. Реализация предиката gcd/3 основана на многократном вычитании меньшего числа из большего, пока два числа не станут равными).
Выполнение работы.
nat_num(0).
nat_num(s(X)):-nat_num(X).

%plus(X,Y,Z): Z - сумма X и Y
plus(0,X,X):-nat_num(X).
plus(s(X),Y,s(Z)):-plus(X,Y,Z).

%ll(X,Y) - истинa, если X<Y
ll(0,X):-X\==0.
ll(s(X),s(Y)):-ll(X,Y). 

%div(X,Y,Z): Z – результат целочисленного деления X на Y
div(X,Y,0):-ll(X,Y),ll(0,Y).
div(s(X),Y,s(Z)):-not ll(s(X),Y),plus(Y,W,s(X)),div(W,Y,Z).


%gcd(X,Y,Z): Z – наибольший общий делитель натуральных чисел X и Y 
gcd(X,X,X):-ll(0,X).
gcd(s(X),s(Y),Z):-ll(s(X),s(Y)),plus(s(X),W,s(Y)),gcd(s(X),W,Z).
gcd(s(X),s(Y),Z):-ll(s(Y),s(X)),plus(s(Y),W,s(X)),gcd(W,s(Y),Z).

%adjacent(X,Y,Zs): X и Y являются соседними элементами в списке Zs
adjacent(X,Y,[Y,X|Zs]).
adjacent(X,Y,[X,Y|Zs]).
adjacent(X,Y,[Z|Zs]):-X\==Z,Y\==Z,adjacent(X,Y,Zs).

%last(X,Xs): X является последним элементом списка Xs
last(X,[X]).
last(Y,[X|Xs]):-Y\==X,last(Y,Xs).

%double(Xs,XsXs): XsXs – список Xs, в котором каждый элемент повторён дважды 
double([X],[X,X]).
double([X|Xs],[X,X|Ys]):-double(Xs,Ys).

%sum(Ns,Sum): Sum – сумма элементов списка натуральных чисел Ns
sum([],0).
sum([0|Xs],Y):-sum(Xs,Y).
sum([s(X)|Xs],s(Y)):-sum([X|Xs],Y).

%substitute(X,Y,L1,L2): L2 – список L1, в котором все вхождения X заменены Y
substitute(X,Y,[],[]).
substitute(X,Y,[X|Xs],[Y|Ys]):-substitute(X,Y,Xs,Ys).
substitute(X,Y,[Z|Xs],[Z|Ys]):-X\==Z,substitute(X,Y,Xs,Ys).
Результаты работы программы.
div(s(s(s(s(0)))),s(s(0)),X)
X = s(s(0)).
1 Solution
gcd(s(s(0)),s(s(s(0))),X)
X = s(0).
1 Solution

gcd(s(s(0)),s(s(s(s(0)))),X)
X = s(s(0)).
1 Solution

adjacent(a,s,[a,s,d])
True
1 Solution
adjacent(d,f,[s,f,d,g])
True
1 Solution

adjacent(g,X,[s,d,f,g,h])
X = f.
X = h.
2 Solutions

last(X,[h])
X = h.
1 Solution

last(X,[k,l,j])
X = j.
1 Solution

double([q,t,r,t],X)
X = [q,q,t,t,r,r,t,t].
1 Solution

sum([s(0),s(s(0)),s(s(s(0)))],X)
X = s(s(s(s(s(s(0)))))).
1 Solution

substitute(m,p,[m,a,m,a],X)
X = [p,a,p,a].
1 Solution

Декларативная интерпретация:
div(X,Y,0):-ll(X,Y),ll(0,Y).
div(s(X),Y,s(Z)):-not ll(s(X),Y),plus(Y,W,s(X)),div(W,Y,Z).

Результатом целочисленного деления меньшего числа на большее будет 0. Целочисленное деление на 0 неопределенно.

s(Z) является результатом целочисленного деления s(X) на Y, если s(X) не меньше Y и из s(X) можно s(Z) раз вычесть число Y из числа s(X).
gcd(X,X,X):-ll(0,X).
gcd(s(X),s(Y),Z):-ll(s(X),s(Y)),plus(s(X),W,s(Y)),gcd(s(X),W,Z).
gcd(s(X),s(Y),Z):-ll(s(Y),s(X)),plus(s(Y),W,s(X)),gcd(W,s(Y),Z).

Наибольший общий делитель пары 0 и 0 не определен.

Z является наибольшим общим делителем натуральных чисел s(X) и s(Y), если при многократном вычитании меньшего числа из большего, оба числа станут равны Z.
adjacent(X,Y,[Y,X|Zs]).
adjacent(X,Y,[X,Y|Zs]).
adjacent(X,Y,[Z|Zs]):-X\==Z,Y\==Z,adjacent(X,Y,Zs).

X и Y являются соседними элементами в списке [Y,X|Zs] и [X,Y|Zs].

X и Y являются соседними элементами в списке [Z|Zs], если X и Y отличны Z и являются соседними элементами в списке Zs.
last(X,[X]).
last(Y,[X|Xs]):-Y\==X,last(Y,Xs).

Последним элементом списка, состоящего из одного элемента, является этот элемент.

Y – последний элемент списка [X|Xs], если Y отличен от Х и является последним элементом списка Xs.
double([],[]).

double([X|Xs],[X,X|Ys]):-double(Xs,Ys).

Удвоение элементов пустого списка в результате дает пустой список.

Список [X,X|Ys] получен из списка [X|Xs] повторением дважды каждого элемента, если список Ys получен из списка Xs после повторения каждого элемента дважды.
sum([],0).
sum([0|Xs],Y):-sum(Xs,Y).
sum([s(X)|Xs],s(Y)):-sum([X|Xs],Y).

Сумма элементов пустого списка равна 0.

Y является суммой элементов списка [0|Xs], если Y – сумма элементов списка Xs.

s(Y) является суммой элементов списка [s(X)|Xs], если Y – сумма элементов списка [X|Xs].
substitute(X,Y,[],[]).
substitute(X,Y,[X|Xs],[Y|Ys]):-substitute(X,Y,Xs,Ys).
substitute(X,Y,[Z|Xs],[Z|Ys]):-X\==Z,substitute(X,Y,Xs,Ys).

Результатом замены всех вхождений элемента Х элементом Y в пустом списке будет пустой список.

Замена вхождений элемента Х элементами Y в списке [X|Xs] приводит к списку [Y|Ys], если замена вхождений элемента Х элементами Y в списке Xs приводит к списку Ys.

Замена вхождений элемента Х элементами Y в списке [Z|Xs], где X отличен от элемента Z, приводит к списку [Z|Ys], если замена вхождений элемента Х элементами Y в списке Xs приводит к списку Ys.

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации