Разделение на голову и хвост
Для этого принято использовать вертикальную черту.
[Head|Tail] ,после применения данной операции в Head – находится “голова”, Tail – находится “хвост”.
Добавление нового элемента
Файл add.pro
/* Добавление нового элемента */
domains
list = integer*
predicates
add_list ( integer, list, list )
clauses
add_list (H,List,[H|List]).
Добавление нового элемента происходит как добавление “головы” к уже существующему списку.
Цели могут быть такими: add_list(1,[2,3],L)
Удаление одного элемента
Файл erase.pro
/* Удаление одного элемента */
domains
list = integer*
predicates
erase_list (list,list)
clauses
erase_list ([H|T],T).
Данная операция противоположна предыдущей, элемент удаляется как “голова” существующего списка.
Цели могут быть такими: erase_list([1,2,3],L)
Поиск элемента в списке
Файл find.pro
/* Поиск элемента */
domains
digit_list=digit *
digit=integer
member_list=member *
member=symbol
predicates
find(digit,digit_list)
find(member,member_list)
clauses
/* Проверяем сходство с “головой” */
find(H,[H|_]).
/* Проверяем сходство с “головой” “хвоста” */
find(H,[_|T]):-find(H,T).
При выполнении поиска происходит последовательный просмотр всех элементов списка с помощью двух предикатов. Первый сопоставляет объект поиска с головой, а следующее правило позволяет сделать доступным для сравнения следующий элемент списка, поскольку он является “головой” нового списка (“хвоста” старого). Если первое правило заканчивается неуспехом, то происходит откат и выполняется второе правило.
Цели могут быть такими: find(1,[1,2,3]); find(“a”,[“v”,”f”,”g”])
Слияние двух списков
Файл concat.pro
/* Слияние двух списков */
domains
all_list=symbol *
predicates
append(all_list,all_list,all_list)
clauses
append([],L,L).
append([N|L1],L2,[N|L3]):-append(L1,L2,L3).
goal
append([t,e],[s,t],L).
Список L1 присоединяется к списку L2, при этом создается список L3, который вначале пуст.
Процесс происходит в следующей последовательности:
1. Пытаясь выполнить первое правило, Пролог раскручивает рекурсию (во втором правиле) до тех пор, пока L1 не станет пустым, а все его элементы не будут находиться в стеке. После этого первое правило будет выполнено и в L3 появяться все элементы L2 (будет выполнено первое правило).
2. Рекурсия начинает сворачиваться и в результате к содержимому L3 будут добавляться элементы из стека (элементы списка L1), это будет происходить до тех пор пока стек не опустеет. В результате L3 содержит элементы обоих списков.
Цели могут быть такими: append([],[s,t],L)
Разделение списков на два.
Файл split.pro
/* Разделение списка на два подсписка */
domains
/* middle – пороговое значение */
middle=symbol
list=symbol *
predicates
split(middle,list,list,list)
clauses
/* Разделение на первый подсписок */
split(Middle,[H|T],[H|L1],L2):-H<=Middle,split(Middle,T,L1,L2).
/* Разделение на второй подсписок */
split(Middle,[H|T],L1,[H|L2]):-split(Middle,T,L1,L2),H>Middle.
split(_,[],[],[]).
Необходимо разделить список по какому-либо признаку, например 1-ый подсписок (L1) заносятся элементы со значениями <= порогового, а во второй (L2) > порогового.
Разделение происходит в следующей последовательности:
1. Текущий элемент из списка сравнивается с порогом, если он <= то записывается в L1.
2. Если элемент > порога, то он помещается в L2.
Цели могут быть такими: split(“c”,[“a”,”b”,”c”],L1,L2); split(“c”,[“a”,”b”,”d”],L1,L2)
Сортировка списка
Файл sort.pro
/* Сортировка списков */
domains
number=integer
list=number *
predicates
insert_sort(list,list)
insert(number,list,list)
asc_order(number,number)
clauses
insert_sort([],[]).
insert_sort([X|T],Sorted_list):-insert_sort(T,Sorted_Tail),
insert(X,Sorted_Tail,Sorted_list).
/* Если X>Y сначала помещаем Y */
insert(X,[Y|Sorted_list],[Y|Sorted_list1]):-
order(X,Y), !,
insert(X,Sorted_list,Sorted_list1).
/* Если X<=Y помещаем X слева от Y */
insert(X,Sorted_list,[X|Sorted_list]).
order(X,Y):-X>Y.
Сортировка выполняется методом вставки, т.е. осуществляется неоднократная вставка элементов в список до тех пор пока он не будет упорядочен.
Процесс упорядочивания элементов следующий:
1. Для успешного выполнения первого insert_sort необходимо обнулить исходный список. При этом значения списка сохраняются в стеке (в результате выполнения второго правила).
2. Рекурсия начинает сворачиваться при этом происходит проверка правил insert, с помощью правила order. В случае неуспеха order рекурсивно вызывает правило insert (для правильной вставки элементов). В результате вставки все элементы в списке оказываются упорядочены.
Цели могут быть такими: insert_sort(1,56,3,5,23,L)
|
Главная
Каталог файлов
