Книга: Программирование на языке Пролог для искусственного интеллекта

Ответы к некоторым упражнениям

Ответы к некоторым упражнениям

1.1

(a) no

(b) X = пат

(c) X = боб

(d) X = боб, Y = пат

1.2

(a) ?- родитель( X, пат).

(b) ?- родитель( лиз, X).

(c) ?- родитель( Y, пат), родитель( X, Y).

1.3

(a) счастлив( X) :- 

    родитель( X, Y).

(b) имеетдвухдетей( X) :- 

    родитель( X, Y),
    сестра( Z, Y).

1.4

внук( X, Z) :-
 родитель( Y, X),
 родитель( Z, Y).

1.5

тетя( X, Y) :-
 родитель( Z, Y),
 сестра( X, Z).

1.6

Да. (Определение верно)

1.7

(a) возвратов не будет

(b) возвратов не будет

(c) возвратов не будет

(d) возвраты будут

2.1

(a) переменная

(b) атом

(c) атом

(d) переменная

(e) атом

(f) структура

(g) число

(h) синтаксически неправильное выражение

(i) структура

(j) структура

2.3

(a) успех

(b) неуспех

(c) неуспех

(d) D = 2, E = 2

(e) P1 = точка(-1, 0) 

   Р2 = точка( 1, 0)
   Р3 = точка( 0, Y)

Такая конкретизация определяет семейство треугольников, у которых две вершины располагаются на оси x в точках 1 и -1, а третья — в произвольной точке оси у.

2.4

отр( точка( 5, Y1), точка( 5, Y2) )

2.5

регулярный( прямоугольник( точка( X1, Y1),
 точка( Х2, Y1), точкa( X2, Y3),
 точка( X1, Y3) ) ).

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

2.6

(a) А = два

(b) no

(c) С = один

(d) D = s(s(1));
   D = s(s(s(s(s(1)))))

2.7

родственники( X, Y) :-
 предок( X, Y);
 предок( Y, X);
 предок( Z, X),
 предок( Z, Y);
 предок( X, Z),
 предок( Y, Z).

2.8

преобразовать( 1, один).
преобразовать( 2, два).
преобразовать( 3, три).

2.9

В случае, изображенном на рис. 2.10, пролог-система выполняет несколько больший объем работы.

2.10

В соответствии с определением сопоставления, приведенном в разд. 2.2, данное сопоставление будет успешным. X приобретает вид циклической структуры, в которой сам X присутствует в качестве одного из аргументов.

3.1

(a) конк( L1, [ _, _, _ ], L)

(b) конк( [ _, _, _ ], L1, L),
     % Удалить 3 первые элемента L
    конк( L2, [ _, _, _ ], L1)
     % Удалить 3 последние элемента L1

Вот более короткий вариант, предложенный I. Tvrdy:

конк( [ _, _, _ | L2], [ _, _, _ ], L)

3.2

(а) последний( Элемент, Список) :- 

   конк( _, [Элемент], Список).

(b) последний( Элемент, [Элемент]).
   последний( Элемент, [Первый | Остальные]):-
    последний( Элемент, Остальные).

3.3

четнаядлина( [] ).
четнаядлина( [Первый | Остальные] ) :-
 нечетнаядлина( Остальные).
нечетнаядлина( [ _ ] ).
нечетнаядлина( [Первый | Остальные] ) :-
 четнаядлина( Остальные).

3.4

обращение( [], []).
обращение( [Первый | Остальные], ОбращСпис): -
 обращение( Остальные, ОбращСписОстальных),
 конк( О6ращСписОстальных, [Первый], ОбращСпис).

3.5

% Такой предикат легко определить при помощи отношения обратить
палиндром( Список) :-
 обратить( Список, Список).
% Вот другое решение, не использующее обратить
палиндром1( [] ).
палиндром1( [ _ ] ).
палиндром1 [Первый | Остальные] ) :-
 конк( Середина, [Первый], Остальные),
 палиндром1( Середина).

3.6

сдвиг( [Первый | Остальные], Сдвинут) :-
 конк( Остальные, [Первый], Сдвинут).

3.7

перевод( [], []).
перевод( [Голова | Хвост], [Голова1 | Хвост1]) :-
 означает( Голова, Голова1),
 перевод( Хвост, Хвост1).

3.8

подмножество( [], [] ).
подмножество( [Первый | Остальные], [Первый | Подмн]):-
  % Оставить первый элемент в подмножестве
 подмножество( Остальные, Подмн).
подмножество( [Первый | Остальные], Подмн) :-
  % Убрать первый элемент из подмножества
 подмножество( Остальные, Подмн).

3.9

разбиениесписка( [], [], []). % Разбивать нечего
разбиениесписка( [X], [X], []).
 % Разбиение одноэлементного списка
разбиениесписка( [X, Y | Список], [X | Список1],
 [Y | Список2]) :-
 разбиениесписка( Список, Список1, Список2).

3.10

можетзавладеть( состояние( _, _, _, имеет), [] ).
  % Ничего не надо делать
можетзавладеть( Состояние, [Действие | Действия]):-
 ход( Состояние, Действие, НовоеСостояние),
  % Первое действие
 можетзавладеть( НовоеСостояние, Действия).
  % Оставшиеся действия

3.11

линеаризация( [Голова | Хвост], ЛинейныйСписок ) :-
  % Линеаризация непустого списка
 линеаризация( Голова, ЛинейнаяГолова ),
 линеаризация( Хвост, ЛинейныйХвост ),
 конк( ЛинейнаяГолова, ЛинейныйХвост,
 ЛинейныйСписок ).
линеаризация( [], [] ). % Линеаризация пустого списка
линеаризация( X, [X] ).
 % Линеаризация объекта, не являющегося списком
% Замечание: при попытке получить от этой программы более
% одного варианта решения выдается бессмыслица

3.12

Терм1 = играет_в( джимми, и( футбол, сквош) )
Терм2 = играет_в( сьюзан, и( теннис,
 и( баскетбол, волейбол) ) )

3.13

:- op( 300, xfx, работает)
:- op( 200, xfx, в)
:- op( 100, xfx, нашем)

3.14

(a) А = 1 + 0

(b) В = 1 + 1 + 0

(c) С = 1 + 1 + 1 + 1 + 0

(d) D = 1 + 1 + 0 + 1

3.15

:- op( 100, xfx, входит_в)
:- op( 300, fx, конкатенация_списков)
:- op( 200, xfx, дает)
:- op( 100, xfx, и)
:- op( 300, fx, удаление_элемента)
:- op( 100, xfx, из_списка) % Принадлежность к списку
Элемент входит_в [Элемент | Список].
Элемент входит_в [Первый | СписокОстальных] :-
 Элемент входит_в СписокОстальных.
% Конкатенация списков
конкатенация_списков [] и Список дает Список.
конкатенация_списков [X | L1] и L2 дает [X | L3] :-
 конкатенация_списков L1 и L2 дает L3.
% Удаление элемента из списка
удаление_элемента Элемент из_списка
 [Элемент | ОстальныеЭлементы]
 дает ОстальныеЭлементы.
удаление_элемента Элемент из_списка
 [Первый | ОстальныеЭлементы]
 дает [Первый | НовСписОстЭлементов] :-
 удаление_элемента Элемент из_списка
 ОстальныеЭлементы дает НовСписОстЭлементов.

3.16

max( X, Y, X) :-
 X >= Y.
max( X, Y, Y) :-
 X <Y.

3.17

максспис( [X], X).
  % Максимум в одноэлементном списке
максспис( [X, Y | Остальные], Мах) :-
  % В списке есть по крайней мере два элемента?
максспис( [Y | Остальные], МаксОстальные),
 mах( X, МаксОстальные, Мах).
  % Мах наибольшее из чисел X и МаксОстальные

3.18

сумспис( [], 0).
сумспис( [Первый | Остальные], Сумма) :-
 сумспис( Остальные, СуммаОстальных),
 Сумма is Первый + СуммаОстальных.

3.19

упорядоченный ([]).
  % Одноэлементный список является упорядоченным
упорядоченный( [X, Y | Остальные] :-
 X =< Y,
 упорядоченный( [Y | Остальные] ).

3.20

подсумма( [], 0, []).
подсумма( [N | Список], Сумма, [N | Подмн]) :-
  % N принадлежит подмножеству
Сумма1 is Сумма - N,
 подсумма( Список, Сумма1, Подмн).
подсумма( [N | Список], Сумма, Подмн) :-
  % N не принадлежит подмножеству
 подсумма( Список, Сумма, Подмн).

3.21

между( N1, N2, N1) :-
 N1 =< N2.
между( N1, N2, X) :-
 N1 < N2,
 HoвoeN1 is N1 + 1,
 между( HoвoeN1, N2, X).

3.22

:- op( 900, fx, если).
:- op( 800, xfx, то).
:- op( 700, xfx, иначе).
:- op( 600, xfx, :=).
если Вел1 > Вел2 то Перем := Вел3
 иначе ЧтоУгодно :-
 Вел1 > Вел2,
 Перем = Вел3.
если Вел1 > Вел2 то ЧтоУгодно
 иначе Перем := Вел4 :-
 Вел1 =< Вел2,
 Перем = Вел4.

4.1

(a) ?- семья(членсемьи( _, Фамилия, _, _ ), _, []).

(b) ?- ребенок( членсемьи( Имя, Фамилия, _,

    работает( _, _ ) )).

(c) семья(членсемьи( _, Фамилия, _, неработает),
    членсемьи( _, _, _, работает( _, _ ) ),_ ).

(d) ?- семья( Муж, Жена, Дети),
    датарождения( Муж, дата( _, _, Год1) ),
    датарождения( Жена, дата( _, _, Год2) ),
    ( Год1 - Год2 >= 15;
      Год2 - Год1 >= 15 ),
    принадлежит( Ребенок, Дети).

4.2

близнецы( Ребенок1, Ребенок2) :-
 семья( _, _, Дети),
 удалить( Ребенок1, Дети, ДругиеДети),
  % Выделить первого ребенка
 принадлежит( Ребенок2, ДругиеДети),
 принадлежит( Ребенок1, Дата),
 принадлежит( Ребенок2, Дата).

4.3

n_элемент( 1, [X | L], X).
  % X - первый элемент списка [X | L]
n_элемент( N, [Y | L], X) :-
  % X - n-й элемент [Y | L]
 N1 is N - 1,
 n_элемент( N1, L, X).

4.4

Входная цепочка укорачивается на каждом неспонтанном цикле, а укорачиваться бесконечно она не может.

4.5

допускается( S, [], _ ) :-
 конечное( S).
допускается( S, [X | Остальные], Макс_переходов) :-
 Макс_переходов > 0,
 переход( S, X, S1),
 НовыйМакс is Макс_переходов - 1,
 допускается( S1, Остальные, НовыйМакс).
допускается( S, Цепочка, Макс_переходов) :-
 Макс_переходов > 0,
 спонтанный( S, S1),
 НовыйМакс is Макс_переходов - 1,
 допускается( S1, Цепочка, НовыйМакс).

4.7

(а) ходконя( X/Y, X1/Y1) :-
     % Ход коня с поля X/Y на поле X1/Y1
    ( dxy( DX, DY);
     % Расстояния по направлениям X и Y
    dxy( DY, DX) ),
     % Или расстояния по направлениям Y и X
    X1 is X + DX,
     % X1 расположен в пределах шахматной доски
    надоске( X1),
    Y1 is Y + DY,
     % Y1 расположен в пределах шахматной доски
    надоске( Y1).
   dxy( 2, 1).   % 2 поля вправо, 1 поле вперед
   dxy( 2, -1).  % 2 поля вправо, 1 поле назад
   dxy( -2, 1).  % 2 поля влево, 1 поле вперед
   dxy( -2, -1). % 2 поля влево, 1 поле назад
   надоске( Коорд) :-
     % Координаты в пределах доски
    0 < Коорд,
    Коорд < 9.

(b) путьконя( [ Поле]). % Конь стоит на поле Поле
   путьконя( [S1, S2 | Остальные] ) :-
    ходконя( S1, S2),
    путьконя( [S2 | Остальные]).

(c) ?- путьконя( [2/1, R, 5/4, S, X/8] ).

5.1

(a) X = 1;
   X = 2

(b) X = 1;
   Y = 1;
   X = 1;
   Y = 2;
   X = 2;
   Y = 1;
   X = 2;
   Y = 2;

(c) X = 1;
   Y = 1;
   X = 1;
   Y = 2;

5.2

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

5.3

разбить( [], [], []).
разбить( [X | L], [X | L1], L2) :-
 X >= 0, !,
 разбить( L, L1, L2).
разбить( [X | L], L1, [X | L2]) .
 разбить( L, L1, L2).

5.4

принадлежит( Некто, Кандидаты),
 not принадлежит( Некто, Исключенные)

5.5

разность( [], _, []).
разность( [X | L1], L2, L):-
 принадлежит( X, L2), !,
 разность( L1, L2, L).
разность( [X | L1], L2, [X | L]) :-
 разность( L1, L2, L).

5.6

унифицируемые( [], _, []).
унифицируемые( [Первый | Остальные], Терм, Список) : -
 not( Первый = Терм), !,
 унифицируемые( Остальные, Терм, Список).
унифицируемые( [Первый | Остальные], Терм,
 [Первый | Список] ) :-
 унифицируемые( Остальные, Терм, Список).

6.1

найтитерм( Терм) :-
  % Пусть текущий входной поток - это файл f
 read( Терм), !,
  % Текущий терм из f сопоставим с Терм'ом?
 write( Терм);      % Если да - вывести его на терминал
  найтитерм( Терм). % В противном случае - обработать

6.2

найтитермы( Терм) :-
 read( ТекущийТерм),
 обработать( ТекущийТерм, Терм).
обработать( end_of_file, _ ) :- !.
обработать( ТекущийТерм, Терм) :-
 ( not( ТекущийТерм = Терм), !;
    % Термы несопоставимы
 write( ТекущийТерм), nl),
  % В противном случае вывести текущий терм
 найтивсетермы( Терм).
  % Обработать оставшуюся часть файла

6.4

начинается( Атом, Символ) :-
 name( Символ, [ Код]),
 name( Атом, [Код | _ ]).

6.5

plural( Существительное, Существительные) :-
 name( Существительное, СписокКодов),
 name( s, КодS),
 конк( СписокКодов, КодS, НовыйСписокКодов),
 name( Существительные, НовыйСписокКодов).

7.2

добавить( Элемент, Список) :-
 var( Список), !,
  % Переменная Список представляет пустой список
Список = [Элемент | Хвост].
добавить( Элемент, [ _ | Хвост]) :-
 добавить( Элемент, Хвост).
принадлежит( X, Список) :-
 var( Список), !,
  % Переменная Список представляет пустой список,
  % поэтому X не может ему принадлежать
 fail.
принадлежит( X, [X | Хвост]).
принадлежит( X, [ _ | Хвост] ) :-
 принадлежит( X, Хвост).

8.2

добавить_в_конец( L1-[Элемент | Z2], Элемент, L1 - Z2).

8.3

обратить( А - Z, L - L) :-
  % Результатом является пустой список,
  % если A-Z представляет пустой список
 А == Z, !.
обратить( [X | L] - Z, RL - RZ ) :-
  % Непустой список
 обратить( L - Z, RL - [X | RZ].

9.1

список( []).
список( [ _ | Хвост]) :-
 список( Хвост).

9.2

принадлежит( X, X затем ЧтоУгодно).
принадлежит( X, Y затем Спис) :-
 принадлежит( X, Спис).

9.3

преобр( [ , ничего_не_делать).
преобр( [Первый | Хвост], Первый затем Остальные):-
 преобр( Хвост, Остальные).

9.4

преобр( [ , ПустСпис, _, ПустСпис).
  % Случай пустого списка
преобр( [Первый | Хвост], НовСпис, Функтор, Пустой) :-
 НовСпис =.. [Функтор, Первый, НовХвост],
 преобр( Хвост, НовХвост, Функтор, Пустой).

9.8

сорт1( [], []).
сорт1( [X], [X]).
сорт1( Спис, УпорСпис) :-
 разбить( Спис, Спис1, Спис2),
  % Разбить на 2 прибл. равных списка
 сорт1( Спис1, Упор1),
 сорт1( Спис2, Упор2),
 слить( Упор1, Упор2, УпорСпис).
  % Слить отсортированные списки
разбить( [], [], []).
разбить( [X], [X], []).
разбить( [X, Y | L], [X | L1], [Y | L2]) :-
  % X и Y помещаются в разные списки
 разбить( L, L1, L2).

9.9

(а) двдерево( nil).
   двдерево( д( Лев, Кор, Прав) ) :-
    двдерево( Лев),
    двдерево( Прав).

9.10

глубина( пусто, 0).
глубина( д( Лев, Кор, Прав), Г) :-
 глубина( Лев, ГЛ),
 глубина( Прав, ГП),
 макс( ГЛ, ГП, МГ),
 Г is МГ + 1.
макс( А, В, А) :-
 А >= В, !.
макс( А, В, В).

9.11

линеаризация( nil, []).
линеаризация( д( Лев, Кор, Прав), Спис) :-
 линеаризация( Лев, Спис1),
 линеаризация( Прав, Спис2),
 конк( Спис1, [Кор | Спис2], Спис).

9.12

максэлемент( д( _, Кор, nil), Кор) :- !.
  % Корень - самый правый элемент
максэлемент( д( _, _, Прав,), Макс) :-
  % Правое поддерево непустое
 максэлемент( Прав, Макс).

9.13

внутри( Элем, д( _, Элем, _ ), [ Элем]).
внутри( Элем, д( Лев, Кор, _ ), [Кор | Путь]) :-
 больше( Кор, Элем),
 внутри( Элем, Лев, Путь).
внутри( Элем,д( _, Кор, Прав), [Кор | Путь]) :-
 больше( Элем, Кор),
 внутри( Элем, Прав, Путь).

9.14

% Отображение двоичного дерева, растущего сверху вниз
% Предполагается, что каждая вершина занимает при печати
% один символ
отобр( Дер) :-
 уровни( Дер, 0, да).
  % Обработать все уровни
уровни( Дер, Уров, нет) :- !.
  % Ниже уровня Уров больше нет вершин
уровни( Дер, Уров, да) :-
  % Обработать все уровни, начиная с Уров
 вывод( Дер, Уров, 0, Дальше), nl,
  % Вывести вершины уровня Уров
 Уров1 is Уров + 1,
 уровни( Дер, Уров1, Дальше).
  % Обработать следующие уровни
вывод( nil, _, _, _, _ ).
вывод( д( Лев, X, Прав), Уров, ГлубХ, Дальше) :-
 Глуб1 is ГлубХ + 1,
 вывод( Лев, Уров, Глуб1, Дальше),
  % Вывод левого поддерева
 ( Уров = ГлубХ, !,
  % X на нашем уровне?
 write( X), Дальше = да;
  % Вывести вершину, продолжить
 write(' ') ),
  % Иначе - оставить место
 вывод( Прав, Уров, Глуб1, Дальше).
  % Вывод левого поддерева

10.1

внутри( Элем, л( Элем)). % Элемент найден в листе
внутри( Элем, в2( Д1, М, Д2) ):-
  % Вершина имеет два поддерева
 больше( М, Элем), !,    % Вершина не во втором поддереве
 внутри( Элем, Д1);      % Поиск в первом поддереве
 внутри( Элем, Д2).      % Иначе - во втором поддереве
внутри( Элем, в3( Д1, M2, Д2, М3, Д3) ):-
  % Вершина имеет три поддерева
 больше( M2, Элем), !,
  % Элемент не во втором и не в третьем поддереве
 внутри( Элем, Д1);      % Поиск в первом поддереве
 больше( M3, Элем), !,   % Элемент не в третьем поддереве
 внутри( Элем, Д2);      % Поиск во втором поддереве
 внутри( Элем, Д3).      % Поиск в третьем поддереве

10.3

avl( Дер) :-
 аvl( Дер, Глуб).  % Дер является AVL-деревом глубины Глуб
avl( nil, 0).      % Пустое дерево - AVL -дерево глубины 0
avl( д( Лев, Кор, Прав), Г) :-
 avl( Лев, ГЛ),
 avl( Прав, ГП),
 ( ГЛ is ГП; ГЛ is ГП + 1; ГЛ is ГП - 1),
  % Глубины поддеревьев примерно совпадают
 макс( ГЛ, ГП, Г).
макс1( U, V, М) :- % М = 1 + макс( U, V)
 U > V, !, М is U + 1;
 М is V + 1.

11.1

вглубину1( [Верш | Путь], [Верш | Путь]) :-
 цель( Верш).
вглубину1( [Верш | Путь], Решение) :-
 после( Верш, Верш1),
 not принадлежит( Верш1, Путь),
 вглубину1( [ Верш1, Верш | Путь], Решение).

11.6

решить( СтартМнож, Решение) :-
  % СтартМнож - множество стартовых вершин
 bagof( [Верш], принадлежит( Верш, СтартМнож),
  Пути),
 вширину( Пути, Решение).

Оглавление книги