Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Предикат отсечения и управление логическим выводом в программахСодержание книги
Поиск на нашем сайте
Управление процессом просмотра предложений является важным аспектом программирования на Прологе. Это осуществляется с помощью специальной встроенной функции «резать», обозначаемой символом "!". Данная встроенная функция может быть использована длядостижения следующих трех целей: 1) исключения бесконечной петли при выполнении программы; 2) программирования взаимоисключающих утверждений; 3) блокирования просмотра целей. Продемонстрируем все три случая на примерах. Пример 1. Устранение бесконечных циклов. Обратимся к утверждениям, определяющим последовательность Фибоначчи (числовая последовательность 1, 1, 2, 3, 5, 8,..., в которой каждое число, начиная с третьего есть сумма двух предыдущих). Программа 118 fib (0,_,1). fib (1,1,1). fib (N,G,H): - fib (N-l,F,G), H is F+G.
На запрос
?- fib (0_,F).
получим F = 1, и Пролог сделает попытку сопоставить с запросом второй факт и потерпит неудачу. Однако сопоставление головы третьего утверждения с запросом происходит успешно и осуществляется попытка доказать цель fib(-l,FO,Fl), что, в свою очередь, приводит к цели fib(-2,..,..) и так далее, т.е. образуется бесконечный цикл. Однако мы можем устранить такие ситуации, используя отсечение и тем самым указывая Прологу, что не существует других решении в случае успешного согласования граничного условия.
Программа 119 fib (0,_,1): -!. fib (1,1,1): -!. fib (N,G,H): - fib (N-l,F,G), H is F+G.
Учитывая данное определение fib и задавая вопрос
?- fib(0_,F).
получаем F=l. Других решений нет. Пример 2. Программирование взаимоисключающих утверждений. Процедуру нахождения наибольшегоиз двух чисел можно записать в виде отношения
max(X, Y, М). Здесь М=Х, если X>=Y, и M=Y, если X<Y. Соответствующие правила таковы:
max(X,Y,X):-X>=Y. max(X, Y, Y): - X<Y.
Эти правила являются взаимоисключающими. Возможна более экономная формулировка, использующая понятие «иначе»:
если X>=Y то М=Х иначе M=Y.
На Прологе это записывается при помощи отсечения:
max(X,Y,X):-X>=Y,! max(X, Y, Y).
Пример 3. Блокирование просмотра целей.
Программа 120 В. D А: - В, С. (1) С: -D,!, Е. (2) Е: -F, G, H. (З) ?А. Говорят, что дизъюнкт (1) «порождает» дизъюнкт (2), так как в правой части (1) есть литера С и эта же литера - в левой части (2). Аналогично дизъюнкт (2) «порождает» дизъюнкт (3). Если (3) неудачен, то в (2) выполнится отсечение: дизъюнкт (2) также считается неудачным, восстанавливается «родительская среда» (1), делается попытка найти альтернативное решение для В. Если бы (2) имело вид С: -D, Е., то при неудаче в (3) была бы сделана попытка найти альтернативное решение для D. В других случаях можетбыть необходимым продолжение поиска дополнительных решений, даже если целевое утверждение уже согласовано. В этих случаях можно использовать встроенный предикат fail. Встроенный предикат fail не имеет аргументов. Он считается всегда ложным. Пример: перебор всевозможных решений.
Программа 121 oc(cpm). ос(msdos). ос(unix). печать-всех:-ос(X), write(X), fail. ?-печать-всех. ОБРАБОТКА СПИСКОВ
На практике часто встречаются задачи, связанные с перечислением объектов. В некоторых случаях при решении задач важно сохранять информацию об уже сделанных шагах решения, чтобы их не повторять. Для решения таких задач в языке Пролог предусмотрены списки. Список можно задать перечислением элементов. Например, имена учеников класса:
[саша,петя,дима,ксюша,лена].
Элементами списка могут быть не только атомы, но и функции, и вообще любые элементы, даже списки. Заранее длина списка не задается, и в ходе выполнения программы она может меняться. Альтернативный способ задания списка использует понятия головы и хвоста списка. Например, в списке [X | Y] Х - это голова списка. Y - его хвост. Хвост списка по определению также является списком. Теперь список может быть определен рекурсивно: 1) пустой список [] - список: 2) [X | Y] - список, если Y - список. Определение списка через его голову и хвост в сочетании с рекурсией лежит в основе большого числа программ, оперирующих списками. Эти программы состоят 1) из факта, ограничивающего рекурсию и описывающего операцию для пустого списка; 2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста (в голове правила), через операцию над хвостом (в подцели). Пример I: определение числа элементов в списке.
Программа 122 сколько ([], 0). сколько ([А|В], N):- сколько (В, М), N is M+1. ?- сколько ([саша, игорь, лена]), X). Ответ: Х=3.
Пример 2: принадлежность элемента списку.
Программа 123 принадлежит (X, [X | Y]). принадлежит (X, [A |Y ]): - принадлежит (X,Y). ?-принадлежит (4,(1,3,4,9]). Ответ:да. Данная программа имеет очень простой декларативный смысл: элемент принадлежит списку, если он является его головой или принадлежит хвосту списка. Пример 3: соединение двух списков. Эту задачу можно описать с помощью следующих предикатов: а) ограничение рекурсии состоит в том, что если к пустому списку [ ] добавить список Р, то в результате получится Р; б) рекурсия состоит в том, что можно список Р добавить к концу списка [X|Y], если Р будет добавлен к хвосту Y и затем присоединен к голове Х (при этом получается список [Х|Т]). Программа 124 присоединить([ ], Р, Р). присоединить([XIY], Р, [X | Т]):-присоединить(Y, Р, Т). ? присоединить(L,[джим.R],(джек,бил,джим,тим,джим,боб]). Ответ: L=[джек,бил]. К=[тим джим,боб]. L=[джек,бил,джим,тим]. R=[бoб]. Существует традиция использовать для обозначения предикатаслияния двух списков предикативный символ append (по-английски -добавить). В некоторых случаях постановки вопросов к такого рода программам приходится использовать отсечение (!). Программа 125 append([ ], L, L). append([A I B], C, [A | D]):- append(B, C, D). ?-append(X,Y,[1,2]). Ответ: X=[] Y=[l,2] X=[l] Y=[2] X=[l,2] Y=[].
Если же заменить первое предложение на append([ ], 1,1):-!. и задать тот же вопрос, то получится правильный ответ:
Х=[] Y=[l,2].
Пример 4. удаление элементов из списка. Программа 126 аналогична проверке принадлежности элемента списку, но требует уже трехарного предиката, один аргумент которого указывает удаляемый элемент, второй аргумент-исходный список и третий - список-результат. Программа 126 удал (X. [X I Y], Y): -!. удал (X. [Z I Y], [Z I W]): - удал (X, Y, W). Декларативный смысл: если удаляемый элемент совпадает с головой списка, то результатом программы является хвост списка, иначе удаления производятся из хвоста списка. Данная программа удаляет первое вхождение в список элемента, связанного с переменной X. Знак отсечения "!"в конце правила предотвращает последующий поиск и вывод лишних вариантов ответов после выполнения ограничительного факта. Для удаления всех вхождений элемента Х программу надо дополнить:
удал (Х,[ ],[]). удал (X, [X | Y], W):- удал (X, Y, W). удал (X, [Z I Y], W):- удал (X, Y, W).
Декларативный смысл программы таков: пока список не пуст, удалить элемент, если он совпадает с головой списка, значит, отбросить голову списка, а затем удалять его из оставшегося хвоста, иначе надо сразу удалять элемент из хвоста. Пример 5: индексация элементов списка. Смысл программы 127 состоит в том, чтобы получить элемент под номером N или узнать номер элемента X.
Программа 127 получить ([X | Y], 1, X). получить ([W | Y], N, X):- N is M+l, получить (Y, M, X). Пример 6: поиск максимального элемента. Программа 128 max ([X], X). max ([X | Y], X):- шах (Y, W), X>W,!. max ([X | Y], W):-max (Y, W). Декларативный смысл программы: если в списке один элемент - он и является максимальным, если более одного, то это голова списка, если она больше максимального элемента хвоста, или максимальный элемент хвоста. Пример 7: обращение списка. Данная задача - самая сложная из рассмотренных. Для ее решения важно сообразить, что обратить список из одного элемента - означает оставить список без изменения. Обратить более длинный список - обратить его хвост, а потом сзади приставить к нему голову исходного списка.
Программа 129 обр ([X], [X]). обр ([X I Y], Z):- обр (Y, W), присоединить (W, [X], Z). В этой программе используется процедура слияния списков, описанная выше. Arity-Prolog располагает значительным числом встроенных предикатов для обработки списков, так что приведенные программы имеют, в основном, учебный характер.
|
||||
Последнее изменение этой страницы: 2016-08-10; просмотров: 355; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.117.107.78 (0.01 с.) |