 |
Написать предикат, который определяет простое число и выводит true, если простое, или false, если наоборот.
|
|
|
|
ЛАБОРАТОРНАЯ РАБОТА №3
ПРЕДСТАВЛЕНИЕ И ОБРАБОТКА СПИСКОВ
Цель работы
Изучение представления списков и программ поиска элемента в списке, разделения и объединения списков, сортировки списка, удаление дубликатов в списке. Разработка программ обработки списков.
Краткие сведения
Список — упорядоченная последовательность элементов. Список — это объекты одного и того же доменного типа. Объектами списка могут быть целые и действительные числа, символы, строки, списки и структуры. Порядок расположения элементов является отличительной чертой списка. Те же самые элементы, упорядоченные иным образом, представляют уже совсем другой список. Порядок элементов и их количество играет важную роль в процессе сопоставления списков. Пролог допускает списки, элементами которых являются структуры.
Элементы списка заключаются в прямоугольные скобки [], а друг от друга отделяются запятыми. Например,
[3, 6, 9, 18, 21, 24, 27, 3, 3]
[3.14, 3.18, 5.12, 15.1]
["Igor", "Anna", "Anton"]
Объекты списка называются элементами списка. Длина списка – количество элементов в списке. Список может содержать произвольное число элементов, единственным ограничением является лишь объем оперативной памяти. Список, не содержащий элементов, называется пустым (нулевым) списком и обозначается []. Непустой список можно рассматривать как состоящий из двух частей:
- первый элемент списка – голова;
- остальная часть списка – хвост.
Голова является элементом списка, хвост есть список сам по себе. Голова – это отдельное неделимое значение. Наоборот, хвост представляет собой список, составленный из того, что осталось от исходного списка в результате отделения головы. Этот список можно делить и дальше. Примеры разделения списков на голову и хвост приведены в табл. 3.1.
|
|
|
Таблица 3.1
| Список | Тип списка | Голова | Хвост |
| [10,20,30,40] | Целые числа | [20,30,40] | |
| ['a', '?', 'z'] | символы | 'a' | ['?', 'z'] |
| ["BOYS"] | символы | "BOYS" | [] |
| [] | –– | Не определен | Не определен |
Применение списков в Пролог-программе
Для использования в программе списка необходимо предварительно описать домен и предикат списка. Описание домена списка производится в разделе domains с указанием звездочки (*) после имени типа элемента списка.
domains
num=integer.
num_list=num*.
или
domains
num_list=integer*.
В разделе описания предикатов predicates требуется присутствие предиката списка. Если одним из его аргументов является список, то за именем этого предиката в круглых скобках указывается имя домена списка на месте соответствующего аргумента.
predicates
number(…, num_list, …).
Работа со списками основана на расщеплении их на голову и хвост. Операция деления списка на голову и хвост обозначается с помощью вертикальной черты '|': [Head|Tail] ([Голова|Хвост]). Пролог позволяет выполнять над списками следующие операции: доступ к элементам списка, проверку на принадлежность к списку, сортировку элементов списка.
Операции над списками
Поиск элемента списка представляет собой просмотр списка с целью выявления соответствия между конкретным объектом и эле-ментами просматриваемого списка. Результатом поиска будет либо успех, либо неуспех. Для сопоставления объекта поиска с элементами просматриваемого списка необходимо построить предикат, аргумен-тами которого являются и объект поиска, и список. Например:
member(2, [3, 4, 5, 8]).
Чтобы выяснить, содержится ли элемент в списке, необходимо установить, эквивалентен ли он голове списка, а если нет, то не является ли он членом хвоста списка, т. е. для организации поиска необходима проверка двух условий:
|
|
|
- искомый элемент Х совпадает с головой списка:
member(X, [X|_]). % или member(X, [Y|_]):- X=Y.
- элемент Х принадлежит хвосту этого списка:
member(X, [_|Y]):- member(X,Y).
Например, нужно установить, существует ли в заданном списке символ 'А':
domains
list = char*
predicates
member(char,list)
clauses
member(X,[X|_]).
member(X,[_|Y]):- member(X,Y).
goal
member('A',['S','B','A','F']), write("yes").
Разделение списка. В случае деления исходного списка L на список L1 (например, для которого элементы меньше значения М) и L2 (значение элементов больше или равно М) вводится предикат
del(M, L, L1, L2).
Организуется правило для разделения: очередной элемент извлекается из списка при помощи метода разделения списка на голову и хвост, а потом сравнивается с М.
Рассмотрим пример, когда нужно разделить исходный список на два по условию:
domains
list=integer*
predicates
del(integer, list, list, list).
clauses
del(M, [H|T], [H|L1], L2):- H<M,
del(M, T, L1, L2).
del(M, [H|T], L1, [H|L2]):- H>=M,
del(M, T, L1, L2).
del(_,[],[],[]).
goal
del(8, [1,2,13,4,18], L1, L2),
write(L1," ",L2).
Результатом будут списки [1,2,4] [13,18].
Объединение списков.
Рассмотрим пример, когда требуется объединить исходные списки L1, L2 в выходной список L3.
domains
list=integer*
predicates
append(list, list, list)
clauses
append([],L,L).
append([N|L1], L2, [N|L3]):-
append(L1, L2, L3).
goal
append([1,2,3],[5,6,7,10],L),
write(L).
Результатом программы будет список [1,2,3,5,6,7,10].
Сортировка списков. Сортировка представляет собой упорядочивание элементов списка определенным образом. Наиболее удобным для реализации в Прологе методом сортировки является метод вставки. Метод реализуется при помощи неоднократной вставки элементов в список до тех пор, пока он не будет упорядочен. Предикат сортировки определяется как
sort(S1,S2).
где S1 – исходный (несортированный) список; S2 – выходной (отсортированный) список.
Если исходный список пуст, то выходной тоже пуст. Пустой список по определению упорядочен. Если же входной список не пуст, то он представляется в виде головы и хвоста списка. Хвост списка сортируется при помощи рекурсивного обращения к sort. Выходной список формируется путем вставки головы списка в отсортированный хвост списка так, чтобы итоговый список был упорядоченным. Вставка осуществляется с помощью предиката
rel(X,S1,S2).
где – X вставляемый элемент, S1 – отсортированный список, в который вставляется элемент X, S2 – отсортированный список, в котором уже присутствует элемент X.
|
|
|
Если S1 непустой список, то его можно представить в виде головы и хвоста списка. Предполагая, что элемент X вставляется в начало списка S1, проверяется, удовлетворяют ли элемент X и голова списка условию упорядоченности. Если условие нарушено (в этом случае предикат cord выполняется), то элемент X вставляется в хвост списка с помощью рекурсивного обращения к предикату rel. Если же условие упорядоченности выполнено (в этом случае предикат cord не выполняется), то происходит переход ко второму предложению процедуры rel, которое осуществляет формирование выходного списка S2 путем вставки элемента X в начало списка S1. Переход ко второму предложению происходит только тогда, когда предикат cord не выполняется, т. к. используется операция отсечения («!») после cord, или же когда список S1 пустой, либо в этом случае выходной список должен состоять из одного вставляемого элемента X.
Рассмотрим пример. Нужно произвести сортировку списка целых чисел в порядке убывания.
domains
number = integer
list = integer*
predicates
sort(list, list).
cord(number, number).
Rel (number, list, list).
clauses
sort([], []).
sort([X|T],S1):-
sort(T,S2), rel(X,S2,S1).
rel(X,[Y|S1],[Y|S2]):-
cord(X,Y),!, rel(X,S1,S2).
rel(X,S1,[X|S1]).
cord(X,Y):- X>Y.
goal
sort([8,6,0,-5,3,7],S),
write(S), nl.
Результатом будет список S=[-5,0,3,6,7,8].
Удаление дублирующих элементов. При работе со списками нередко возникают списки с дублирующимися элементами. В связи с этим возникает задача удаления дубликатов из списка. Для ее решения можно предложить предикат
delete(S1,S2).
где S1 – исходный список, возможно содержащий дубликаты, S2 – выходной список без дубликатов.
Если исходный список пустой, то выходной тоже пустой. Если же исходный список не пустой, то он представляется в виде головы и хвоста списка и происходит проверка, принадлежит ли голова списка хвосту. Если да, то это значит, что в хвосте есть дубликаты головы, и тогда выходной список формируется из хвоста списка. Если же нет, это значит, что голова дубликатов не имеет. В этом случае (т.к. использована операция отсечения «!») происходит переход ко второму предложению, включающему голову списка в выходной список и формирующему хвост выходного списка из хвоста исходного списка. Для проверки принадлежности элемента хвосту списка используется описанный ранее предикат member.
|
|
|
Рассмотрим пример. Пусть требуется удалить из списка дубликаты элементов.
domains
listS = symbol*
predicates
delete(listS, listS).
member(symbol, listS).
clauses
delete([],[]).
delete([X|S1],S2):-
member(X,S1),!, delete(S1,S2).
delete([X|S1],[X|S2]):-
delete(S1,S2).
member(X,[X|_]).
member(X,[_|T]):- member(X,T).
goal
delete([igor, anna, oleg, igor, alina, igor,
masha, anna],L),
write(L), nl.
Результатом работы программы будет список
L=["oleg","alina","igor","masha","anna"].
Если же нужно удалить в списке не все вхождения определенного элемента, а только первое, то можно воспользоваться процедурой
delete_one(_,[],[]).
delete_one(X,[X|L],L):–!.
delete_one(X,[Y|L],[Y|L1]):–
delete_one(X,L,L1).
Варианты заданий
Задание. Задан список целых чисел L.
1. Сформировать список L1 из положительных элементов L.
2. Сформировать список L1 из отрицательных элементов L.
3. Сформировать список L1 из элементов L, удовлетворяющих равенствам 
.
4. Сформировать список L1 из элементов L, стоящих на четных местах.
5. Сформировать список L1 из элементов L, стоящих на нечетных местах.
6. Сформировать список L1 из четных чисел списка L.
7. Сформировать список L1 из нечетных чисел списка L.
8. Сформировать список L1 из чисел списка L, кратных k.
9. Сформировать список L1 из элементов: сумма всех n элементов, сумма первых 
элементов L и т. д.
10. Сформировать список L1 из элементов: произведение всех n элементов, произведение первых элементов L и т. д.
11. Сформировать список L1 из элементов: сумма всех n элементов, сумма последних элементов L и т. д.
12. Сформировать список L1 из элементов: произведение всех n элементов, произведение последних элементов L и т. д.
13. Сформировать список L1 из элементов: сумма положительных элементов всего списка L, сумма положительных элементов из первых элементов списка L и т. д.
14. Сформировать список L1 из элементов: сумма отрицательных элементов всего списка L, сумма отрицательных элементов из первых элементов списка L и т. д.
15. Сформировать список L1 из элементов: максимальный элемент всего списка L, максимальный элемент среди первых элементов L и т. д.
16. Сформировать список L1 из элементов: минимальный элемент всего списка L, минимальный элемент среди первых элементов L и т. д.
17. Сформировать список L1 из элементов: максимальный элемент всего списка L, максимальный элемент среди последних элементов L и т. д.
18. Сформировать список L1 из элементов: минимальный элемент всего списка L, минимальный элемент среди последних элементов L и т. д.
|
|
|
19. Сформировать список L1 из элементов: максимальный среди отрицательных элементов всего списка L, максимальный среди отрицательных элементов из первых элементов L и т. д.
20. Сформировать список L1 из элементов: минимальный среди положительных элементов всего списка L, минимальный среди положительных элементов из первых элементов L и т. д.
21. Сформировать список L1 из элементов: максимальный среди отрицательных элементов всего списка L, максимальный среди отрицательных элементов из последних элементов L и т. д.
22. Сформировать список L1 из элементов: минимальный среди положительных элементов всего списка L, минимальный среди положительных элементов из последних элементов L и т. д.
23. Сформировать список L1 из элементов: L сдвинутый циклически на одну позицию влево, L сдвинутый циклически на две позиции влево и т. д.
24. Сформировать список L1 из элементов: L сдвинутый циклически на одну позицию вправо, L сдвинутый циклически на две позиции вправо и т. д.
25. Сформировать список L1 из всех перестановок списка L (без дублирования).
ЛАБОРАТОРНАЯ РАБОТА №4
СОРТИРОВКА СПИСКОВ
Цель работы
Изучение способов сортировки целочисленных списков.
|
|
|
