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

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.

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

    Х - победитель, если
        X победил некоторого Y и
        Х не был побежден никем.

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

        Если Х победил кого-либо и Х был кем-то
                     побежден,
        то Х - боец,
        иначе,    если Х победил кого-либо,
                       то Х - победитель,
                       иначе,     если Х был кем-то побежден,
                                      то Х - спортсмен.

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

        класс( X, боец) :-
             победил( X, _ ),
             победил( _, X),  !.

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

        класс( X, спортсмен) :-
             победил( _, X).

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

Упражнения

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

        р( 1).
        р( 2) :-  !.
        р( 3).

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

    (a)        ?-  р( X).
    (b)        ?-  р( X),   p(Y).
    (c)        ?-  р( X),   !,  p(Y).

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

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

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

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

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

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

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

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

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

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

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


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