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( [Верш], принадлежит( Верш, СтартМнож),
Пути),
вширину( Пути, Решение).
Чем выше приоритет, тем меньше его номер. — Прим. перев.
