Информатика -продвинутый курс



         

ОБРАБОТКА СПИСКОВ - часть 2


б) рекурсия состоит в том, что можно список Р добавить к концу списка [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).

Декларативный смысл программы таков: пока список не пуст, удалить элемент, если он совпадает с головой списка, значит, отбросить голову списка, а затем удалять его из оставшегося хвоста, иначе надо сразу удалять элемент из хвоста.




Содержание  Назад  Вперед