Программирование на языке Пролог для искусственного интеллекта [Иван Братко] (fb2) читать постранично, страница - 151
[Настройки текста] [Cбросить фильтры]
Глава 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.
Последние комментарии
13 часов 28 минут назад
13 часов 28 минут назад
1 день 51 минут назад
1 день 52 минут назад
1 день 2 часов назад
1 день 2 часов назад