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

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( [Верш], принадлежит( Верш, СтартМнож),

 Пути),

 вширину( Пути, Решение).