Назад | Содержание| Вперёд 5. 2. Примеры, использующие отсечение em...

Назад | Содержание| Вперёд

5. 2. Примеры, использующие отсечение

5. 2. 1. Вычисление максимума

Процедуру нахождения наибольшего из двух чиселможно запрограммировать в виде отношения

mах( X, Y, Мах)

где Мах = X, если Х больше или равен Y, и Мах есть Y, если Х меньше Y. Это соответствует двум такимпредложениям:

mах( X, Y, X) :- Х >= Y.

max( X, Y, Y) :- Х < Y.

Эти правила являются взаимно исключающими.Если выполняется первое, второе обязательнопотерпит неудачу. Если неудачу терпит первое,второе обязательно должно выполниться. Поэтомувозможна более экономная формулировка,использующая понятие "иначе":

если Х >= Y, то Мах = X,

иначе Мах = Y.

На Прологе это записывается при помощиотсечения:

mах( X, Y, X) :- Х >= Y, !.

mах( X, Y, Y).

5. 2. 2. Процедура проверкипринадлежности списку, дающая единственноерешение

Для того, чтобы узнать, принадлежит ли Х спискуL, мы пользовались отношением

принадлежит( X, L)

Программа была следующей:

принадлежит( X, [X | L]).

принадлежит X, [Y | L] ):- принадлежит( X, L).

Эта программа дает "недетерминированный"ответ: если Х встречается в списке несколько раз,то будет найдено каждое его вхождение. Исправитьэтот недостаток не трудно: нужно толькопредотвратить дальнейший перебор сразу же послетого, как будет найден первый X, а это произойдет,как только в первом предложении наступит успех.Измененная программа выглядит так:

принадлежит( X, [X | L] ):- !.

принадлежит( X, [Y | L] ):- принадлежит( X, L).

Эта программа породит только одно решение.Например:

?- принадлежит( X,[а, b, с] ).

Х = а;

nо (нет)

5. 2. 3. Добавление элемента ксписку, если он в нем отсутствует (добавление бездублирования)

Часто требуется добавлять элемент Х в список Lтолько в том случае, когда в списке еще нет такогоэлемента. Если же Х уже есть в L, тогда L необходимооставить без изменения, поскольку нам не нужнылишние дубликаты X. Отношение добавитьимеет три аргумента:

добавить( X, L, L1)

где Х - элемент, который нужно добавить, L -список, в который его нужно добавить, L1 -результирующий новый список. Правила добавленияможно сформулировать так:

если Х принадлежит к L,то L1 = L,

иначе L1 - это список L сдобавленным к нему

элементом X.

Проще всего добавлять Х в начало списка L так,чтобы Х стал головой списка L1. Запрограммироватьэто можно так:

добавить( X, L, L) :-принадлежит( X, L), !.

добавить( X, L, [X | L] ).

Поведение этой процедуры можнопроиллюстрировать следующим примером:

?- добавить( а,[b,с], L).

L = [a, b, c]

?- до6авить( X, [b,с], L).

L = [b, с]

Х = b

?- добавить( а, [b,с, X], L).

L = [b, с, а]

Х = а

Этот пример поучителен, поскольку мы не можемлегко запрограммировать "недублирующеедобавление", не используя отсечения иликакой-либо другой конструкции, полученной изнего. Если мы уберем отсечение в только чторассмотренной программе, то отношение добавитьбудет добавлять дубликаты элементов, ужеимеющихся в списке. Например:

?- добавить( a, [a, b,c], L),

L = [а, b, с]

L = [а, а, b, с]

Поэтому отсечение требуется здесь дляправильного определения отношения, а не толькодля повышения эффективности. Этот моментиллюстрируется также и следующим примером.

5. 2. 4. Задача классификации объектов

Предположим, что у нас есть база данных,содержащая результаты теннисных партий,сыгранных членами некоторого клуба. Подбор парпротивников для каждой партия не подчинялсякакой-либо системе, просто каждый игроквстречался с несколькими противниками.Результаты представлены в программе в видефактов, таких как

победил( том, джон).

победил( энн, том).

победил( пат, джим).

Мы хотим определить

отношение класс(Игрок, Категория)

которое распределяет игроков по категориям. Унас будет три категории:

победитель - любой игрок,победивший во всех сыгранных им играх

боец - любой игрок, внекоторых играх победивший, а в некоторыхпроигравший

спортсмен - любой игрок,проигравший во всех сыгранных им партиях

Например, если в нашем распоряжении есть лишьприведенные выше результаты, то ясно, что Энн иПат - победители. Том - боец и Джим - спортсмен.

Легко сформулировать правило для бойца:

Х - боец, если существует некоторый Y,такой, что Х победил

Y, и

существует некоторый Z,такой, что Z победил

Теперь правило для победителя:

Х - победитель, если

X победил некоторого Y и

Х не был побежден никем.

Эта формулировка содержит отрицание "не",которое нельзя впрямую выразить при помощи техвозможностей Пролога, которыми мы располагаем кнастоящему моменту. Поэтому оказывается, чтоформулировка отношения победительдолжна быть более хитрой. Та же проблемавозникает и при формулировке правил дляотношения спортсмен. Эту проблему можнообойти, объединив определения отношений победительи боец и использовав связку"иначе". Вот такая формулировка:

Если Х победил кого-либои Х был кем-то

побежден,

то Х - боец,

иначе, если Хпобедил кого-либо,

то Х - победитель,

иначе, если Х был кем-то побежден,

то Х - спортсмен.

Такую формулировку можно сразу перевести наПролог. Взаимные исключения трех альтернативныхкатегорий выражаются при помощи отсечений:

класс( X, боец) :-

победил(X, _ ),

победил(_, X), !.

класс( X, победитель):-

победил(X, _ ), !.

класс( X, спортсмен):-

победил(_, X).

Заметьте, что использование отсечения впредложении для категории победительне обязательно, что связано с особенностяминаших трех классов.

Упражнения

5. 1. Пусть есть программа:

р( 1).

р( 2) :- !.

р( 3).

Напишите все ответы пролог-системы наследующие вопросы:

(a) ?- р(X).

(b) ?- р( X), p(Y).

Посмотреть ответ

5. 2. Следующие отношенияраспределяют числа на три класса - положительные,нуль и отрицательные:

класс( Число,положительные) :- Число > 0.

класс( 0, нуль).

класс( Число,отрицательные) :- Число < 0.

Сделайте эту процедуру более эффективной припомощи отсечений.

Посмотреть ответ

5. 3. Определите процедуру

разбить( Числа,Положительные, Отрицательные)

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

разбить( [3, -1, 0, 5, -2],[3, 0, 5], [-1, -2] )

Предложите две версии: одну с отсечением,другую - без.

Посмотреть ответ

Назад | Содержание| Вперёд

Оглавление