Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Обработка списков
На практике часто встречаются задачи, связанные с перечислением объектов. В некоторых случаях при решении задач важно сохранять информацию об уже сделанных шагах решения, чтобы их не повторять. Для решения таких задач в языке Пролог предусмотрены списки. Список можно задать перечислением элементов. Например, имена учеников класса:
[саша,петя,дима,ксюша,лена].
Элементами списка могут быть не только атомы, но и функции, и вообще любые элементы, даже списки. Заранее длина списка не задается, и в ходе выполнения программы она может меняться. Альтернативный способ задания списка использует понятия головы и хвоста списка. Например, в списке [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 располагает значительным числом встроенных предикатов для обработки списков, так что приведенные программы имеют, в основном, учебный характер.
|