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

Братко Иван

Глава 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, Дальше).

% Обработать следующие уровни