Навигация
Главная
Поиск
Форум
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
Создание отчето... 64233
Модуль Forms 63954
Пример работы с... 61065
ТЕХНОЛОГИИ ДОСТ... 60843
Имитационное мо... 56376
Реклама
Сейчас на сайте
Гостей: 8
На сайте нет зарегистрированных пользователей

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

Калькулятор на Delphi с переводом в другую систему исчисления + Блок схемы
Моделирование работы аэропорта на GPSS + Пояснительная записка
Моделирование процесса передачи данных по магистрали с основным и резерв...

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
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 10 2009 01:12:44 · 0 Комментариев · 11099 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
База игр
3D Тетрис [Исходн...
Averaging [Исходн...
Профессиональное ...
PDA версия сайта
Java Server Pages...
Allsubmitter 4.7 ...
Мониторинг сервер...
AJAX и PHP. разра...
BDEPack
Pro-Download Sys...
Учебник по создан...
Интерактивный инт...
Приемы программир...
CS:Source - монит...
Калькулятор [Исхо...
CoolDev TipsSyste...
Размещение элемен...
IPAddresseEdit
CoolHints2k v1.03

Топ загрузок
Приложение Клие... 100455
Delphi 7 Enterp... 86160
Converter AMR<-... 20072
GPSS World Stud... 12525
Borland C++Buil... 11612
Borland Delphi ... 8526
Turbo Pascal fo... 7035
Visual Studio 2... 4992
Калькулятор [Ис... 4744
FreeSMS v1.3.1 3539
Случайные статьи
Деструктор
Подари себе Интерн...
Высокий трафик не ...
Наследование конк...
Минимизация открыт...
Убираем защиту в W...
Символические ссылки
Очереди имеют след...
Шаблоны и наследов...
История языков про...
Исключения
Методы обработки д...
Некоторые операции...
сверку с CRL (рис
Идея «витала в воз...
Изменения в SVR4.1/ES
Глава 2. Эпизод из...
Параметры шаблона ...
Инструменты автома...
File access denied
Для изменения фона...
Раздел описания ти...
Урок 3. Продолжаем...
Список ссылок поис...
Символы, используе...
Статистика



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


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