Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 65383
Модуль Forms 65160
Пример работы с... 64247
ТЕХНОЛОГИИ ДОСТ... 61804
Имитационное мо... 57719
Реклама
Сейчас на сайте
Гостей: 8
На сайте нет зарегистрированных пользователей

Пользователей: 13,083
новичок: tesli
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование процесса обработки заданий на вычислительном центре на GP...
Изменения контуров и сортировка в двумерном массиве чисел на Turbo Pasca...
Лабораторная работа по динамическим спискам на Turbo Pascal (перемещение...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
7.1. Словарь в виде упорядоченного дерева


Предположим, что мы хотим установить отношения между элементами информации с тем, чтобы использовать их, когда потребуется. Например, толковый словарь ставит в соответствие слову его определение, а словарь иностранного языка ставит в соответствие слову на одном языке слово на другом языке. Мы уже познакомились с одним способом составления словаря: с помощью задания фактов. Если нам нужно составить таблицу выигрышей на скачках, проводившихся на Британских островах в течение 1938 г., то мы можем просто определить факты вида выигрыши(Х, Y) , где X - кличка лошади, a Y – количество гиней (денежных единиц), выигранных этой лошадью. Следующая база данных может рассматриваться как часть этой таблицы:
Выигрыши(abaris,582).
Выигрыши(careful,17).
Выигрыши(jingling_silvee,300).
Bыигрыши(majola,356).



Если мы хотим узнать, какую сумму выиграла лошадь по кличке maloja, нам нужно просто правильно построить вопрос и Пролог даст нам ответ:
?- Bыигрыши(maloja, X).
X=356



Напомним, что Пролог просматривает базу данных сверху вниз. Это значит, что если база данных нашего словаря упорядочена в алфавитном порядке, как в приведенном выше примере, то на поиск суммы выигрыша для ablaze Пролог затратит меньше времени, чем на поиск суммы выигрыша для zoltan. Однако хотя Пролог способен просмотреть свою базу данных гораздо быстрее, чем вы сможете просмотреть напечатанную таблицу, неразумно просматривать таблицу с начала до конца, если известно, что данные искомой лошади расположены в самом конце. Точно так же, хотя в Прологе имеются специальные средства быстрого просмотра базы данных, он не всегда проходит так быстро, как хотелось бы. В зависимости от размеров таблицы и от того, сколько информации хранится о каждой лошади, Прологу может потребоваться на просмотр таблицы неприемлемо большое время.
По этим и другим причинам специалисты по информатике потратили немало сил на поиски хороших способов организации хранения таких данных, как таблицы и словари. Сам Пролог использует некоторые из этих методов внутри себя при организации хранения своих собственных фактов и правил, но иногда их полезно использовать и в наших программах. Мы рассмотрим один такой метод организации словаря, который называется методом упорядоченного дерева. Метод упорядоченного дерева является одновременно и эффективным способом использования словаря и средством демонстрации того, насколько полезны списки структур.
Упорядоченное дерево состоит из некоторого числа структур, называемых узлами, причем каждому входу словаря соответствует один узел. Каждый узел содержит четыре компоненты. Сюда входят два связанных с узлом элемента данных, как в предикате выигрыши в вышеприведенном примере. Один из этих элементов называется ключом, его имя определяет место в словаре (кличка лошади в нашем примере). Другой элемент используется для хранения какой-либо другой информации о данном объекте (сумма выигрыша в нашем примере). Кроме того, каждый узел содержит ссылку (наподобие ссылки на хвост списка) на узел со значением ключа, которое лексикографически (по алфавиту) меньше, чем имя, являющееся ключом данного узла, а также еще одну ссылку на узел со значением ключа лексикографически большим, чем имя, являющееся ключом данного узла. Будем использовать структуру, которую обозначим как в(Л,В,М, Б) (в - сокращение от «выигрыши»), где Л – кличка лошади (атом), используемая в качестве ключа, В – сумма выигрыша в гинеях (целое), М – структура, соответствующая лошади, кличка которой меньше, чем та, что хранится в Л , а Б  – структура, соответствующая лошади, кличка которой больше, чем значение в Л . Когда для М и Б нет соответствующих структур, мы не будем их конкретизировать. Для небольшого множества лошадей указанная структура, будучи записанной в виде дерева, могла бы иметь вид, как представлено на рис. 7.1.
Если записать ее на Прологе в ступенчатом виде, учитывая ширину страницы, то она могла бы выглядеть так:
в(massinga,858,
  в(braermar,385,
    в(adela,588,_,_),
    _),
   в(panorama,158,
     в(nettleweed,579,_,_),
     _).
).



Теперь, располагая такой структурой, мы хотим «просмотреть» ее по кличкам лошадей, чтобы узнать их выигрыши в течение 1938 г. Как и раньше, структура должна иметь формат в(Л,В,М, Б). Условие окончания поиска состоит в том, что кличка искомой лошади должна совпасть с Л . В этом случае поиск удачен и не требуется пробовать другие варианты. В противном случае мы должны использовать предикат меньше, определенный в гл. 3, чтобы определить, какую из «ветвей» дерева, М или Б , нужно рекурсивно просмотреть. Мы используем эти принципы при определении предиката искать, причем искать(Л,Т, Г) означает, что лошадь Л, если она найдена в таблице Т (которая организована в виде структуры формата в), выиграла Г гиней:
искать (Л, в(Л,Г,_,),Г):- !.
искать Л, в(Л1,_,До,_),Г):-меньше(Л,Л1),искать(Л,До,Г).
искать(Л, в(Л1,_,_,После),Г):- not (меньше(Л,Л1)), искать(Л,После,Г).



Если при поиске по упорядоченному дереву использовать этот предикат, то в общем случае проверок будет меньше, чем если бы их данные были организованы в виде простого списка и просматривались бы с начала до конца.
Предикат искать обладает одним интересным и удивительным свойством: когда вводим вопрос о лошади, клички которой нет в структуре, то любая информация, содержащаяся в вопросе, остается зафиксированной в этой структуре после окончания поиска. Иными словами, вопрос
?- искать(ruby_vintage,S,X).



имеет следующую интерпретацию: построить структуру в, в которой кличке ruby_vintage поставлен в соответствие выигрыш X , и присвоить ее в качестве значения переменной S . Таким образом, искать осуществляет вставку новых компонент в частично заданную структуру. Поэтому многократно обратившись к искать, можно построить словарь. Например, вопрос
?- искать(abaris,X,582), искать(maloja,X,356).



привел бы к тому, что значение переменной X стало упорядоченным деревом из двух вхождений.
Понять то, каким образом искать одновременно выполняет и создание и выборку компонент, можно на основе тех знаний о Прологе, которыми вы уже располагаете; мы настоятельно рекомендуем разобраться в этом самостоятельно. Подсказка: если искать(Л,Т, Г) используется в конъюнкции целей, то «изменения» в структуре Т сохраняются только в области определения Т.
Упражнение 7.1. Поэкспериментируйте с предикатом искать, чтобы установить, какие различия будут в словаре, если элементы в него вставлять каждый раз в разном порядке. Например, как будет выглядеть дерево словаря, если вставлять его элементы в таком порядке: massinga, braemar nettleweed, panorama? А если в таком порядке: adela, braemar, nettleweed, massinga?

http://www.topvirus.ru/all_antivirus/antivirus/dl/9 - — один из наиболее эффективных программных продуктов для защиты компьютера от различного вредоносного ПО и вирусов.
Опубликовал Kest July 10 2009 01:09:26 · 0 Комментариев · 8338 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Программа предназ...
Упорядоченный дин...
Delphi 2005. Разр...
ScreenSaver [Исхо...
База для Allsubmi...
CoolDev TipsSyste...
WinPopup
Простой пример ка...
Berg
Фундаментальные а...
CoolHints2k v1.03
CoolHints2k
Text3D
Cooltray
Усложнённый кальк...
CarGame [Исходник...
Редактор текста (...
Время загрузки ...
Определние размер...
Report

Топ загрузок
Приложение Клие... 100468
Delphi 7 Enterp... 87024
Converter AMR<-... 20078
GPSS World Stud... 12793
Borland C++Buil... 11819
Borland Delphi ... 8600
Turbo Pascal fo... 7039
Visual Studio 2... 4999
Калькулятор [Ис... 4795
FreeSMS v1.3.1 3542
Случайные статьи
Дополнительные пар...
Опции публикации
Объединение путей.1
Кнопка фиксации ав...
ПРИЛОЖЕНИЕ 5. Карт...
Версия Windows XP
Тестирование модул...
Множественный дост...
Веселый отдых
Развертывание ЦС п...
Точный перечень ме...
Добавление медиафа...
Основы перетаскива...
Генерация HTTP зап...
Программирование: ...
Результаты работы ...
Определите тип инф...
Создание потоков. ...
Табл. 13-14.
Создание нового эл...
INTERFACE expected
Создание трояна в ...
Содержание
Поиск минимума фун...
Модуль List
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?