Материал: Методическое пособие по Turbo Prolog (новое)

Для описания этого предиката в разделе goal программы можно использовать конструкцию:

show :- dogs(X), print_list(X).

Если необходимо установить наличие некоторого элемента в списке, то применяется правило:

find_it( X,[X| _ ]).

find_it( X,[ _ |Y]):- find_it( X,[Y]).

В первом описании происходит сравнение объекта поиска и головы текущего списка. Если это сравнение неуспешно, то происходит откат и попытка повторения со вторым вариантом.

Программа 14

DOMAINS dog_list=symbol*

PREDICATES dogs(dog_list). find_it(symbol,dog_list).

GOAL

find_it(«болонка»,[«лайка», «дог» ]),write(“да”). CLAUSES

find_it(X,[X,_]). find_it(X,[_,Y]):-find_it(X,[Y]).

Первое правило описывает ситуацию, когда искомый элемент Х совпадает с головой списка.

Второе правило используется при неуспехе первого правила и описывает новый вызов первого правила, но уже с усеченным списком, в котором нет первого элемента и т.д. Если в списке нет элементов (пустой список), то второе правило оказывается неуспешным.

Программа не напечатает Yes, поскольку болонки нет в списке собак.

Следующий пример производит подсчет суммы всех элементов списка чисел.

Программа 15

DOMAINS spisok=integer*

PREDICATES summa_sp(spisok,integer)

21

CLAUSES summa_sp([],0).

summa_sp([H|T],S):-summa_sp(T,S1),S= H +S1.

Рассмотрим операцию слияния двух списков.

Пусть L1 и L2 – две переменные, представляющие входные списки. L3 – выходной список, получаемый слиянием L1 и L2.

append([ ],L,L).

append( [N|L1], L2, [N|L3] ):- append(L1, L2, L3).

Первый вариант этого правила выполняется когда первый список пустой, второй работает в остальных случаях.

Рассмотрим использование этого предиката при следующем вызове:

append([1,2,3], [4,5],_).

Здесь первый вариант правила сначала не работает, так как первый список не пустой.

Начинает работать второе правило, так как третий список пустой, к нему не применима операция деления на голову и хвост. Что касается первого списка, то он в процессе рекурсивных вызовов претерпевает деления на голову и хвост, и в конце концов становится пустым (его элементы попадают в стек)

append([ ],[4,5],_).

После этого срабатывает первый вариант правила, и третий список инициализируется вторым:

append([ ],[4,5], [4,5]).

И, наконец, чтобы завершить рекурсивные вызовы, ПРОЛОГ извлекает из стека (в обратном порядке) элементы первого списка и возвращает их, в соответствии с описанием второго варианта правила, в списки 1 и 3:

append([1,2,3], [4,5],[1,2,3,4,5]).

Рассмотрим, как используются списки и механизм рекурсии при решении известной задачи о мужике, волке, козе и капусте.

22

go(state(east,east,east,east),state(west,west,west,west)), write(“solved press any key to continue”),

readchar(_), exit.

CLAUSES go(S,G):-

path(S,G,[S],L), nl,write(“A solution is:”),nl, write_path(L),

fail. go(_,_).

path(S,G,L,L1):- move(S,S1), not( unsafe(S1) ), not( member(S1,L) ), path( S1,G,[S1|L],L1),!.

path(G,G,T,T):- !. /* Конечное состояние найдено, список L копируется в L1*/ move(state(X,X,G,C),state(Y,Y,G,C)):-opposite(X,Y). /* мужик и волк */ move(state(X,W,X,C),state(Y,W,Y,C)):-opposite(X,Y). /* мужик и коза */ move(state(X,W,G,X),state(Y,W,G,Y)):-opposite(X,Y). /* мужик и капуста */ move(state(X,W,G,C),state(Y,W,G,C)):-opposite(X,Y). /* один мужик */

opposite(east,west).

opposite(west,east):-!. /* описание противоположных сторон */

23

member(X,[X|_]).

member(X,[_|L]):-member(X,L) /* проверка состояний, которые уже были */

write_path( [H1,H2|T] ) :- !,

readchar(_), write_move(H1,H2), write_path([H2|T]). write_path( [ ] ).

write_move( state(X,W,G,C), state(Y,W,G,C) ) :-!, write(“ Мужик пересекает реку с”,X,” на “,Y),nl. write_move( state(X,X,G,C), state(Y,Y,G,C) ) :-!, write(“ Мужик везет волка с “,X,” берега на “,Y),nl. write_move( state(X,W,X,C), state(Y,W,Y,C) ) :-!, write(“ Мужик везет козу с”,X,” берега на “,Y),nl. write_move( state(X,W,G,X), state(Y,W,G,Y) ) :-!, write(“ Мужик везет капусту с “,X,” берега на “,Y),nl.

8. РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ

Способности к описанию логических задач являются наиболее сильной стороной ПРОЛОГа.

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

Рассмотрим простую логическую задачу. Пример:

«В велосипедных гонках три первых места заняли Алеша, Петя и Коля. Какое место занял каждый из них, если Петя занял не второе и не третье место, а Коля – не третье?»

Решение задачи заключается в установлении зависимости между спортсменами и местами, которую можно описать табл. 2 (прочерки указывают известную информацию):

24

Очевидно, Петя может занимать только первое место, тогда Коля – только второе, а Алеше достается третье (табл. 3).

При описании этой задачи на ПРОЛОГе получается следующая программа.

Программа 17

PREDICATES name(symbol) mesto(symbol) prizer(symbol,symbol)

solution(symbol,symbol,symbol,symbol,symbol,symbol) CLAUSES

name(alex). name(pier). name(nike). mesto(odin). mesto(dva). mesto(tri).

prizer(X,Y):-name(X),mesto(Y),X=pier,not(Y=dva),not(Y=tri); name(X),mesto(Y),X=nike,not(Y=tri); name(X),mesto(Y),not(X=pier),not(X=nike). solution(X1,Y1,X2,Y2,X3,Y3):-name(X1),name(X2),name(X3),

mesto(Y1),mesto(Y2),mesto(Y3),prizer(X1,Y1), prizer(X2,Y2), prizer(X3,Y3),Y1<>Y2,Y2<>Y3,Y1<>Y3, X1<>X2,X2<>X3,X1<>X3,!.

Конечно, в приведенном примере быстрее использовать таблицу для получения решения. Однако в более сложных случаях таблицы становятся многомерными. Рассмотрим еще один пример – логическую задачу (“Наука и жизнь” №3 , 1968):

25