Навигация
Главная
Поиск
Форум
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
21 ошибка прогр... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Имитационное мо... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Реклама
Сейчас на сайте
Гостей: 18
На сайте нет зарегистрированных пользователей

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

Игра Sokoban на Delphi + Блок схемы
Обратное размещение элементов ЭВС на Delphi + Пояснительная записка
Метод половинного деления для нахождения корня уровнения на Turbo Pascal...

7.5. Обработка списков


В этом разделе мы рассмотрим некоторые основные предикаты, полезные при работе со списками. Поскольку Пролог позволяет работать с произвольными структурами данных, списки не могут играть в нем той незаменимой роли, какая им отводится в других языках программирования, таких, как Лисп и Поп-2. Однако независимо от того, будут или не будут использоваться списки в ваших программах, всегда важно представлять себе, как работают предикаты, определения которых рассматриваются в данном разделе, поскольку они основаны на принципах, которые применимы при работе с любыми структурами данных.
Нахождение последнего элемента списка: Цель последний(X, L) согласуется с базой данных, если элемент X является последним элементом списка L . Граничное условие выполняется, когда список L содержит только один элемент. Это условие проверяется первым правилом. Второе правило задает общий рекурсивный случай:
последний(Х,[Х]).
последний(Х,[_,|Y]):- последний(Х,Y).
?- последний(Х,[talk,of,the,town]).
X = town



Проверка порядка следования элементов: Цель следомза(Х, Y, L) согласуется с базой данных, если элементы X и Y являются последовательными элементами списка L . Особенности работы переменных допускают, чтобы или X , или Y , или обе переменные были неконкретизированы перед попыткой согласовать цель. В первом утверждении, которое проверяет граничное условие, должно быть также предусмотрено, что после X и Y в списке могут быть другие элементы. Этим объясняется появление анонимной переменной, в которой сохраняется хвост списка:
следомза(Х,Y,[Х,Y|_]).
следомза(Х,Y,[_|Z]):- следомза(Х,Y,Z).



Объединение списков: С приводимым примером мы уже встречались ранее в разд. 3.6. Цель присоединить(X, Y, Z) согласуется с базой данных в том случае, если Z – это список, построенный путем добавления Y в конец X . Например,
?- присоединить([a,b,с],[d,e,f],Q).
Q=[a,b,c,d,e,f]



Определение предиката присоединить выглядит следующим образом:
присоединить([],L,L).
присоединить([Х|L1],L2,[Х|LЗ]):- присоединить(L1,L2,LЗ).



Граничное условие выполняется тогда, когда первый аргумент является пустым списком. Действительно, пополнение какого-либо списка пустым списком не изменяет его. В дальнейшем мы постепенно приближаемся к граничному условию, поскольку каждое рекурсивное обращение к присоединить удаляет один элемент из головы первого аргумента.
Заметим, что любые два аргумента присоединить могут быть конкретизированы, и в этом случае присоединить конкретизирует третий аргумент соответствующим результатом. Этим свойством, которое можно было бы назвать «недетерминированным программированием», обладают многие из определяемых в данной главе предикатов. Указанная гибкость присоединить позволяет определить с его помощью ряд других предикатов, что мы и сделаем:
последний(Е1,Список):- присоединить(_,[Е1],Список).
следомза(Е11,Е12,Список):-
присоединить(_,[Е11,Е12|_], Список).
принадлежит(Е1,Список):- присоединить(_,[Е1|_],Список).



Обращение списка: Цель обр(L,M) согласуется с базой данных, если результат перестановки в обратном порядке элементов списка L есть список М . В программе используется стандартный прием, когда обращенный список получается присоединением его головы к обращенному хвосту. Лучший способ обратить хвост – это использовать сам обр. Граничное условие выполняется тогда, когда первый аргумент сократился до пустого списка, в этом случае результатом также является пустой список:
обр([],[]).
обр([Н|Т],L):- обр(T,Z), присоединить(Z,[Н],L).



Заметим, что на месте второго аргумента присоединить стоит Н в квадратных скобках. Причина в том, что Н – это голова первого аргумента, а голова списка сама не обязана быть списком. Хвост же списка по определению всегда является списком. Для более эффективной реализации обр мы можем встроить действия по объединению списков непосредственно в утверждения для обр:
o6p2(L1,L2):- обрдоп(L1,[],L2).
обрдоп([X|L],L2 f L3):- обрдоп(L,[Х|L2],LЗ).
обрдоп([],L,L).



Второй аргумент обрдоп используется для хранения «текущего результата». Каждый раз, когда выявляется новый фрагмент результата (X) , передаваемый в остальную часть программы, «текущий результат» представляет из себя старый «текущий результат», дополненный новым фрагментом X . В самом конце последний «текущий результат» возвращается в качестве результата исходного целевого утверждения. Аналогичный прием используется в разд. 7.8 при определении предиката имя_целого.
Исключение одного элемента: Цель исключ1(Х, Y,Z) исключает первое вхождение элемента X из списка Y , формируя новый сокращенный список Z . Если в списке Y нет элемента X , то целевое утверждение недоказуемо. Граничное условие выполняется тогда, когда мы находим искомый элемент X , иначе осуществляется рекурсивная обработка хвоста списка Y :
исключ1(А,[А|L],L):-!.
исключ1(А,[В|L],[В|М]):- исключ1(А,L,М).



Легко добавить утверждение, которое обеспечит доказательство предиката, когда второй аргумент сократится до пустого списка. Это утверждение, реализующее новое граничное условие, есть исключ1(_,[],[])-
Исключение всех вхождений некоторого элемента; Цель исключить(Х, L1, L2) создает список L2 путем удаления всех элементов X из списка L1 . Граничное условие выполняется тогда, когда L1 является пустым списком. Это означает, что мы рекурсивно исчерпали весь список. Если X находится в голове списка, то результатом является хвост этого списка, из которого X тоже удаляется. Последний случай возникает, если во втором аргументе обнаружено, что-то отличное от X. Тогда мы просто входим в новую рекурсию.
исключить(_, [],[]).
исключить(Х,[Х|L],М):-!, исключить(Х,L,М).
исключить(Х,[Y|L1],[Y|L2]):- исключить(Х,L1,L2).



Замещение: Этот предикат очень напоминает исключить, с той лишь разницей, что вместо удаления искомого элемента мы заменяем его некоторым другим элементом. Цель заменить(Х, L,A,M) строит новый список М из элементов списка L , при этом все элементы X заменяются на элементы А . Здесь возможны 3 случая. Первый, связанный с граничным условием, в точности совпадает с тем, что было в исключить. Второй случай – когда в голове второго аргумента содержится элемент X , а третий – когда там содержится нечто отличное от X :
заменить(_,[],_,[]).
заменить(Х,[Х|L],А,[А|М]):-!, заменить(Х,L,А,М).
заменить(Х,[Y|L],А,[Y|М]):- заменить(Х,L,А,М).



Подсписки: Список X является подсписком списка Y , если каждый элемент X содержится и в Y с сохранением порядка следования и без разрывов. Например, доказуемо следующее:
подсписок[[собрание, членов, клуба],[общее, собрание, членов, клуба, будет, созвано, позже]).



Программа подсписок требует двух предикатов: один для нахождения совпадения с первым элементом, и второй, чтобы убедиться, что остальная часть первого аргумента поэлементно совпадает с соответствующей частью второго аргумента.
подсписок([Х|L],[Х|М]):- совпало(L,M),!.
подсписок(L,[_|М]):- подсписок(L,M).
совпало([],_).
совпало([Х|L],[Х|М]):- совпало(L,М).



Отображение: Это мощный метод, заключающийся в преобразовании одного списка в другой с применением к каждому элементу первого списка некоторой функции и использованием ее результата в качестве очередного элемента второго списка. Программа преобразования одного предложения в другое, которая рассматривалась в гл. 3, является одним из примеров отображения. Мы говорим, что «отображаем одно предложение в другое».
Отображение настолько полезно, что заслуживает отдельного раздела. Кроме того, поскольку списки в Прологе – это просто частные случаи структур, мы отложим обсуждение отображения списков до разд. 7.12. Отображение многолико. В разд. 7.11, посвященном символическому дифференцированию, описывается способ отображения одного арифметического выражения в другие.

Компьютерная помощь. Компания IT Beat специализируется на услугах IT аутсорсинга в Москве и Московской области, http://www.itbeat.ru/ проверенное средство повышения эффективности ведения бизнеса и снижения расходов на технический персонал.
Опубликовал Kest July 09 2009 21:12:44 · 0 Комментариев · 12525 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Профессиональное ...
C++ Builder в за...
Progressbar
ZipTV
Упорядоченный дин...
Tetris 2002
PHP: обучение на ...
Основы Delphi. Пр...
WebReg v1.3
Flash MP3 Player ...
HtmlLerz PRO
ICQ
Tank [Исходник на...
Turbo Pascal for ...
Delphi и технолог...
Strawberry Prolog...
Язык программиров...
DirHTMLReportBuil...
Искусство програм...
PBEditPack

Топ загрузок
Приложение Клие... 100772
Delphi 7 Enterp... 97809
Converter AMR<-... 20261
GPSS World Stud... 17014
Borland C++Buil... 14189
Borland Delphi ... 10267
Turbo Pascal fo... 7372
Калькулятор [Ис... 5972
Visual Studio 2... 5206
Microsoft SQL S... 3661
Случайные статьи
В качестве первого...
Простая блокировка...
Блок синхронизации
Интересная тема дл...
Игровые автоматы. ...
Метафора
пользователям
ТАБЛИЦЫ
Предикат, вычисляю...
Маршрутизаторы
Increase Quotas (У...
Что есть у большин...
5.1.2. Ввод термов
Импорт статических...
Способы организаци...
Инструкция по сбор...
Кроме того, через ...
Основное различие ...
Блоки организации ...
включите для учетн...
Методы выделения т...
Новое казино Vulca...
Задачи клиентского...
Мастер списков
Инфографика для но...
Статистика



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


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