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

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

Пути),

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

Чем выше приоритет, тем меньше его номер. — Прим. перев .