Решение логических задач в ПРОЛОГе

ПРОЛОГ позволяет наиболее естественным образом решать логические задачи, моделируя процесс размышления человека с помощью правил.

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

Пример 1

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

Решение

Традиционным способом задача решается заполнением таблицы. По условию задачи Петя занял не второе и не третье место, а Коля - не третье. Это позволяет поставить символ '-' в соответствующих клетках.

 

Имя	I место	II место	III место
Алеша
Петя		-	-
Коля			-

Между множеством имен участников гонки и множеством мест должно быть установлено взаимнооднозначное соответствие. Поэтому определяем занятое место сначала у Пети, затем у Коли и, наконец, у Алеши. В соответствующих клетках проставляем знак '+'. В каждой строке и каждом столбце должен быть только один такой знак.

 

Имя	I место	II место	III место
Алеша	-	-	+
Петя	+	-	-
Коля	-	+	-

Из последней таблицы следует, что Алеша занял третье место, Петя - первое, Коля - второе.

Программа на ПРОЛОГе будет выглядеть следующим образом:

PREDICATES

имя(string)

место(string)

соответствие(string,string)

решение(string,string,string,string,string,string)

CLAUSES

имя(алеша).

имя(петя).

имя(коля).

место(первое).

место(второе).

место(третье).

/* Устанавливаем взаимнооднозначное соответствие

между множеством имен и множеством мест, X - имя,Y - место */

/* Петя занял не второе и не третье место */

соответствие(X, Y):-имя(X), X=петя,

место(Y),not(Y=второе),

not(Y=третье).

/* Коля занял не третье место */

соответствие(X, Y):- имя(X), X=коля,

место(Y), not(Y=третье).

соответствие(X, Y):- имя(X), X=алеша, место(Y).

/* У всех ребят разные места */

решение(X1,Y1,X2,Y2,X3,Y3):-

X1=петя,соответствие(X1,Y1),

X2=коля,соответствие(X2,Y2),

X3=алеша,соответствие(X3,Y3),

Y1<>Y2, Y2<>Y3, Y1<>Y3.

GOAL

решение(X1,Y1,X2,Y2,X3,Y3), write(X1," - ",Y1),nl,

write(X2," - ",Y2),nl,write(X3," - ",Y3),nl.

Результат выполнения программы

петя - первое

коля - второе

алеша - третье

 

Пример 2

Наташа, Валя и Аня вышли на прогулку, причем туфли и платье каждой были или белого, или синего, или зеленого цвета. У Наташи были зеленые туфли, а Валя не любит белый цвет. Только у Ани платье и туфли были одного цвета. Определить цвет туфель и платья каждой из девочек, если у всех туфли и платья были разного цвета.

Решение

PREDICATES

имя(string)

туфли(string)

платье(string)

соот(string,string,string)

решение(string,string,string,string,string,string,

string,string,string)

CLAUSES

имя(наташа).

имя(валя).

имя(аня).

туфли(белый).

туфли(синий).

туфли(зеленый).

платье(белый).

платье(синий).

платье(зеленый).

% X – имя, Y – цвет туфель, Z – цвет платья

соот(X,Y,Z):-имя(X),туфли(Y),платье(Z),

X=наташа,Y=зеленый,Y<>Z.

соот(X,Y,Z):-имя(X),туфли(Y),платье(Z),

X=валя,not(Y=белый),

not(Z=белый), Y<>Z.

соот(X,Y,Z):-имя(X),туфли(Y),платье(Z),X=аня,Y=Z.

решение(X1,Y1,Z1,X2,Y2,Z2,X3,Y3,Z3):-

X1=наташа,соот(X1,Y1,Z1),

X2=валя, соот(X2,Y2,Z2),

X3=аня, соот(X3,Y3,Z3),

Y1<>Y2, Y2<>Y3, Y1<>Y3,

Z1<>Z2, Z2<>Z3, Z1<>Z3.

GOAL

решение(X1,Y1,Z1,X2,Y2,Z2,X3,Y3,Z3),

write(X1," туфли- ",Y1," платье- ",Z1),nl,

write(X2," туфли- ",Y2," платье- ",Z2),nl,

write(X3," туфли- ",Y3," платье- ",Z3),nl.

Результат выполнения программы

наташа туфли - зеленый платье - синий

валя туфли - синий платье - зеленый

аня туфли - белый платье - белый

Пример 3

Витя, Юра и Миша сидели на скамейке. В каком порядке они сидели, если известно, что Миша сидел слева от Юры, а Витя слева от Миши.

Решение

PREDICATES

слева(string,string)

ряд(string,string,string)

CLAUSES

/* Миша сидел слева от Юры */

слева(миша, юра).

/* Витя сидел слева от Миши */

слева(витя, миша).

/* Объекты X, Y и Z образуют ряд,

если Х слева от Y и Y слева от Z */

ряд(X, Y, Z):- слева(X,Y), слева(Y, Z).

GOAL

ряд(X, Y, Z), write(X,"-",Y,"-",Z),nl.

Результат выполнения программы

витя-миша-юра

 

Пример 4

Известно, что тополь выше березы, которая выше липы. Клен ниже липы, а сосна выше тополя и ниже ели. Определить самое высокое и самое низкое дерево.

Решение

DOMAINS

name=string

PREDICATES

выше(name,name)

ряд(name,name,name,name,name,name)

CLAUSES

выше(тополь,береза).

выше(липа,клен).

выше(ель,сосна).

выше(береза,липа).

выше(сосна,тополь).

ряд(X1,X2,X3,X4,X5,X6):-выше(X1,X2),выше(X2,X3),

выше(X3,X4),выше(X4,X5),

выше(X5,X6).

GOAL

ряд(X,_,_,_,_,Y),write("Самое высокое - ",X),nl,

write("Самое низкое - ",Y),nl.

 

Результат выполнения программы

Самое высокое - ель

Самое низкое - клен

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Трое ребят вышли гулять с собакой, кошкой и хомячком. Известно, что Петя не любит кошек и живет в одном подъезде с хозяйкой хомячка. Лена дружит с Таней, гуляющей с кошкой. Определить, с каким животным гулял каждый из детей.

2. Беседуют трое друзей: Белокуров, Рыжов и Чернов. Брюнет сказал Белокурову: «Любопытно, что один из нас блондин, другой – брюнет, а
третий – рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос у каждого из друзей?

3. Витя, Юра, Миша и Дима сидели на скамейке. В каком порядке они сидели, если известно, что Юра сидел справа от Димы, Миша справа от Вити, а Витя справа от Юры.

4. Известно, что Волга длиннее Амударьи, а Днепр короче Амударьи. Лена длиннее Волги. Определить вторую по протяженности реку.

Отчет о выполненной самостоятельной работе должен содержать:

1) тему лабораторной работы;

2) условие задачи;

3) решение задачи традиционным способом (с помощью таблицы);

4) листинг программы;

5) результаты ее тестирования с различными исходными данными.

Списки

Список – это объект, который содержит конечное число других объектов. Список в ПРОЛОГе заключается в квадратные скобки и элементы списка разделяются запятыми. Список, который не содержит ни одного элемента, называется пустым списком.

Список является рекурсивным объектом. Он состоит из головы (первого элемента списка) и хвоста (все последующие элемента). Хвост также является списком. В ПРОЛОГе имеется операция “|”, которая позволяет делить список на голову и хвост. Пустой список нельзя разделить на голову и хвост.

Тип данных "список" объявляется в программе на Прологе следующим образом:

DOMAINS

списковый_тип = тип*

где "тип" - тип элементов списка; это может быть как стандартный тип, так и нестандартный, заданный пользователем и объявленный в разделе DOMAINS ранее.

Основными операциями на списками являются:

- формирование списка;

- объединение списков;

- поиск элемента в списке;

- вставка элемента в список и удаление из списка.

-

Пример 1

Сформировать список вида [7,6,5,4,3,2,1]

Решение

DOMAINS

list = integer*

PREDICATES

genl(integer, list)

CLAUSES

genl(0,[]):-!.

genl(N,[N|L]):-N1=N-1, genl(N1,L).

GOAL

genl(7,L),write(L),nl.

Результат выполнения программы:

[7,6,5,4,3,2,1]

Пример 2

Сформировать список из N элементов, начиная с 2. Каждый следующий на 4 больше предыдущего.

Решение

DOMAINS

list = integer*

PREDICATES

genl(integer, integer, list)

CLAUSES

genl(N2,N2,[]):-!.

genl(N1,N2,[N1|L]):-N1<N2, N=N1+4,

genl(N,N2,L).

GOAL

write("N="),readint(N),K=4*(N+1)-2,

genl(2,K,L),write(L),nl.

Результат выполнения программы:

N=5

[2,6,10,14,18]

Пример 3

Сформировать список последовательных натуральных чисел от 4 до 20 и найти количество его элементов.

Решение:

DOMAINS

list = integer*

PREDICATES

genl1(integer, integer, list)

len(integer, list)

CLAUSES

genl1(N2,N2,[]):-!.

genl1(N1,N2,[N1|L]):-N1<N2, N=N1+1, genl1(N,N2,L).

len(0,[]).

len(X,[_|L]):-len(X1,L), X=X1+1.

GOAL

genl1 (4,21,L),write(L),nl,

len(X, L),write("Количество элементов=",X),nl.

Результат выполнения программы:

[4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

Количество элементов=17

 

Пример 4

Определить, содержится ли введенное число Х в заданном списке L.

Решение:

DOMAINS

list = integer*

PREDICATES

member(integer, list)

CLAUSES

member(X,[X|_]):-write("yes"),!.

member(X,[]):-write("no"),!.

member(X,[_|L]):- member(X, L).

GOAL

L=[1,2,3,4], write(L),nl, write("X="),readint(X),

member(X, L),nl.

Результат выполнения программы:

1-й случай:

[1,2,3,4]

X=3

yes

2-й случай:

[1,2,3,4]

X=5

no

 

Пример 5

Сформировать списки L1=[1,2,3], L2=[10,11,12,13,14,15] и объединить их в список L3.

Решение:

DOMAINS

list = integer*

PREDICATES

genl1(integer,integer,list)

append(list,list,list)

CLAUSES

genl1(N2,N2,[]):-!.

genl1(N1,N2,[N1|L]):-N1<N2,N=N1+1,genl1(N, N2, L).

append([],L,L).

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

GOAL

genl1(1,4,L1),write("L1=",L1),nl,

genl1(10,16,L2),write("L2=",L2),nl,

append(L1,L2,L3),write("L3=",L3),nl.

Результат выполнения программы:

L1=[1,2,3]

L2=[10,11,12,13,14,15]

L3=[1,2,3,10,11,12,13,14,15]

Пример 6

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

Решение:

DOMAINS

list = symbol*

PREDICATES

del(symbol,list,list)

CLAUSES

del(X,[X|L],L).

del(X,[Y|L],[Y|L1]):-del(X,L,L1).

GOAL

L=[пн, вт, ср, чт, пт, сб, вс],write("L=",L),nl,

write("X="),readln(X),

del(X,L,L1),write("L1=",L1),!;

write("Элемент отсутствует в списке"),nl.

Результат выполнения программы:

1-й случай:

L=["пн","вт","ср","чт","пт","сб","вс"]

X=ср

L1=["пн","вт","чт","пт","сб","вс"]

2-й случай:

L=["пн","вт","ср","чт","пт","сб","вс"]

X=пр

Элемент отсутствует в списке

Пример 7

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

Решение:

DOMAINS

list = symbol*

PREDICATES

del(symbol,list,list)

ins(symbol,list,list)

CLAUSES

del(X,[X|L],L).

del(X,[Y|L],[Y|L1]):-del(X,L,L1).

ins(X,L1,L):-del(X,L,L1).

GOAL

L=[olga, oksana, toma, dima],write("L=",L),nl,

write("X="),readln(X),

ins(X,L,L1),write("L1=",L1),nl, fail.

Результат выполнения программы:

L=["olga","oksana","toma","dima"]

X=vera

L1=["vera","olga","oksana","toma","dima"]

L1=["olga","vera","oksana","toma","dima"]

L1=["olga","oksana","vera","toma","dima"]

L1=["olga","oksana","toma","vera","dima"]

L1=["olga","oksana","toma","dima","vera"]

 

Пример 8

Найти сумму элементов списка целых чисел.

Решение:

DOMAINS

list=integer*

PREDICATES

sum_list(list, integer)

CLAUSES

sum_list([],0).

sum_list([X|L],S):-sum_list(L,S1),S=S1+X.

GOAL

L=[1,2,3,4,5],sum_list(L,S), write("S=",S).

Результат выполнения программы:

S=15

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Сформировать список [2, 4, 6, 8, 10] и удалить из него введенное число.

2. Сформировать списки [1, 3, 5, 7, 9] и [2, 4, 6, 8, 10] и объединить их в один.

3. Сформировать список [3, 6, 9, 12, 15, 18] и вставить в него введенное число.

4. Сформировать список из N натуральных чисел, начиная с 10. Каждое следующее на 5 больше предыдущего.

5. Сформировать список [3, 6, 9, 12, 15] и найти сумму его элементов

6. Сформировать список [6, 5, 4, 3, 2] и найти сумму его элементов

7. Сформировать список [7, 5, 3, 1] и найти произведение его элементов

8. Сформировать список из N последовательных натуральных чисел, начиная с 10. Найти сумму его элементов

Отчет о выполненной самостоятельной работе должен содержать:

1) тему лабораторной работы;

2) условие задачи;

3) листинг программы;

4) результаты ее тестирования.