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

добкор( nil, X, дер( nil, X, nil) ). % Ввести X в пустое дерево

добкор( дер( L, Y, R), X, дер( L1, X, дер( L2, Y, R) )) :-

 больше( Y, X),

 добкор( L, X, дер( L1, X, L2) ).

добкор( дep( L, Y, R), X, дep( дep( L, Y, R1), X, R2) ) :-

 больше( X, Y),

 добкор( R, X, дер( R1, X, R2) ).

Рис. 9.15. Внесение элемента на произвольный уровень двоичного справочника.

Эта процедура обладает тем замечательным свойством, что в нее не заложено никаких ограничений на уровень дерева, в который вносится новый элемент. В связи с этим операцию добавить можно использовать "в обратном направлении" для удаления элемента из справочника. Например, приведенная ниже последовательность целей строит справочник Д, содержащий элементы 3, 5, 1, 6, а затем удаляет из него элемент 5, после чего получается справочник ДД:

добавить( nil, 3, Д1), добавить( Д1, 5, Д2),

добавить( Д2, 1, Д3), добавить( Д3, 6, Д),

добавить( ДД, 5, Д).

<p>9.4. Отображение деревьев</p>

Так же, как и любые объекты данных в Прологе, двоичное дерево T может быть непосредственно выведено на печать при помощи встроенной процедуры write. Однако цель

write( T)

хотя и отпечатает всю информацию, содержащуюся в дереве, но действительная структура дерева никак при этом не будет выражена графически. Довольно утомительная работа — пытаться представить себе структуру дерева, рассматривая прологовский терм, которым она представлена. Поэтому во многих случаях желательно иметь возможность отпечатать дерево в такой форме, которая графически соответствует его структуре.

Существует относительно простой способ это сделать. Уловка состоит в том, чтобы изображать дерево растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким образом, чтобы корень стал его крайним слева элементом, а листья сдвинулись вправо (рис. 9.16).

Рис. 9.16. (а) Обычное изображение дерева. (b) То же дерево, отпечатанное процедурой отобр (дуги добавлены для ясности).

Давайте определим процедуру

отобр( T)

так, чтобы она отображала дерево в форме, показанной на рис. 9.16. Принцип работы этой процедуры:

Для того, чтобы отобразить непустое дерево T, необходимо:

(1) отобразить правое поддерево дерева T с отступом вправо на расстояние H;

(2) отпечатать корень дерева T;

(3) отобразить левое поддерево дерева T с отступом вправо на расстояние H.

Величина отступа H, которую можно выбирать по желанию, — это дополнительный параметр при отображении деревьев. Введем процедуру

отобр2( T, H)

печатающую дерево T с отступом на H пробелов от левого края листа. Связь между процедурами отобр и отобр2 такова:

отобр( T) :- отобр2( T, 0).

На рис. 9.17 показана программа целиком. В этой программе предусмотрен сдвиг на 2 позиции для каждого уровня дерева. Описанный принцип отображения можно легко приспособить для деревьев других типов.

отобр( T) :-

 отобр2( T, 0).

отобр2( nil, _ ).

отобр2( дер( L, X, R), Отступ) :-

 Отступ2 is Отступ + 2,

 отобр2( R, Отступ2),

 tab( Отступ), write( X), nl,

 отобр( L, Отступ2).

Рис. 9.17. Отображение двоичного дерева.

Упражнение

9.14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья — справа. Напишите (более сложную) процедуру для отображения дерева, ориентированного обычным образом, т.е. с корнем наверху и листьями внизу. 

<p>9.5. Графы </p><p>9.5.1. Представление графов</p>

Графы используются во многих приложениях, например для представления отношений, ситуаций или структур задач. Граф определяется как множество вершин вместе с множеством ребер, причем каждое ребро задается парой вершин. Если ребра направлены, то их также называют дугами. Дуги задаются упорядоченными парами. Такие графы называются направленными. Ребрам можно приписывать стоимости, имена или метки произвольного вида, в зависимости от конкретного приложения. На рис. 9.18 показаны примеры графов.

В Прологе графы можно представлять различными способами. Один из них — каждое ребро записывать в виде отдельного предложения. Например, графы, показанные на рис. 9.18, можно представить в виде следующего множества предложений:

связь( а, b).

связь( b, с).

Перейти на страницу:

Похожие книги

Adobe InDesign CS3
Adobe InDesign CS3

Книга посвящена верстке и макетированию в программе Adobe InDesign CS3. Помимо того что в ней описываются возможности программы, рассматриваются также принципы и традиции верстки, приводятся примеры решения типичных задач. Все это позволит читателю не только овладеть богатым инструментарием программы, но и грамотно применять его.Материал книги разделен на логические части: теоретические сведения, инструментарий программы, решение задач, – а также рассчитан на два уровня подготовки читателей – начинающих и опытных пользователей, что выгодно отличает книгу от других изданий. Это позволит применять ее как новичкам для знакомства с программой, так и пользователям со стажем для пополнения своих знаний.

Владимир Гавриилович Завгородний , Владимир Завгородний

Программирование, программы, базы данных / Программное обеспечение / Книги по IT
C++
C++

С++ – это универсальный язык программирования, задуманный так, чтобы сделать программирование более приятным для серьезного программиста. За исключением второстепенных деталей С++ является надмножеством языка программирования C. Помимо возможностей, которые дает C, С++ предоставляет гибкие и эффективные средства определения новых типов. Используя определения новых типов, точно отвечающих концепциям приложения, программист может разделять разрабатываемую программу на легко поддающиеся контролю части. Такой метод построения программ часто называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определенных пользователем. Такие объекты просты и надежны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. Программирование с применением таких объектов часто называют объектно-ориентированным. При правильном использовании этот метод дает более короткие, проще понимаемые и легче контролируемые программы. Ключевым понятием С++ является класс. Класс – это тип, определяемый пользователем. Классы обеспечивают сокрытие данных, гарантированную инициализацию данных, неявное преобразование типов для типов, определенных пользователем, динамическое задание типа, контролируемое пользователем управление памятью и механизмы перегрузки операций. С++ предоставляет гораздо лучшие, чем в C, средства выражения модульности программы и проверки типов. В языке есть также усовершенствования, не связанные непосредственно с классами, включающие в себя символические константы, inline-подстановку функций, параметры функции по умолчанию, перегруженные имена функций, операции управления свободной памятью и ссылочный тип. В С++ сохранены возможности языка C по работе с основными объектами аппаратного обеспечения (биты, байты, слова, адреса и т.п.). Это позволяет весьма эффективно реализовывать типы, определяемые пользователем. С++ и его стандартные библиотеки спроектированы так, чтобы обеспечивать переносимость. Имеющаяся на текущий момент реализация языка будет идти в большинстве систем, поддерживающих C. Из С++ программ можно использовать C библиотеки, и с С++ можно использовать большую часть инструментальных средств, поддерживающих программирование на C. Эта книга предназначена главным образом для того, чтобы помочь серьезным программистам изучить язык и применять его в нетривиальных проектах. В ней дано полное описание С++, много примеров и еще больше фрагментов программ.

Бьёрн Страуструп , Бьярн Страустрап , Мюррей Хилл

Программирование, программы, базы данных / Программирование / Книги по IT