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

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

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

Глава 1

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

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

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

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

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

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

7.2

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

Глава 8

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

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

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

11.1

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

11.6

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

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


Генерация: 0.379. Запросов К БД/Cache: 3 / 0
поделиться
Вверх Вниз