 |
Краткие сведения и примеры программ
|
|
|
|
Списки, с которыми будем работать, могут быть представлены в разделе описания доменов следующим образом:
domains
listI = integer*
Пример 4.1. Создать предикат, позволяющий вычислить сумму элементов списка.
Так как в пустом списке элементов нет, сумма элементов пустого списка равна нулю. Для вычисления суммы элементов непустого списка нужно к сумме элементов хвоста добавить первый элемент списка.
sum([], 0). % сумма элементов пустого списка равна 0
sum([H|T], S):–
sum(T, S_T), % S_T – сумма элементов хвоста,
S = S_T + H. % S – сумма элементов исходного списка
.Предикат, позволяющий вычислить сумму элементов списка можно написать, используя накопитель, в котором хранится полученная сумма. Сперва накопитель пуст. Переходя от вычисления суммы непустого списка к вычислению суммы элементов его хвоста, добавить первый элемент к уже насчитанной сумме. Когда список опустеет, передать полученную сумму (результат) в третий аргумент.
sum_list([],S,S). % список пуст, значит в накопителе
% сумма элементов списка
sum_list([H|T],N,S):–
N_T=H+N, % N_T – результат добавления к сумме,
% находящейся в накопителе, первого
% элемента списка.
sum_list(T,N_T,S). % предикат от хвоста T и N_T
Если нужно вызвать предикат от двух аргументов, а не от трех, то можно создать вспомогательный предикат:
sum2(L,S):– sum_list(L,0,S).
Последний вариант реализует хвостовую рекурсию.
Пример 4.2. Создать предикат, вычисляющий среднее арифметическое элементов списка.
Воспользуемся предикатами, вычисляющими количество и сумму элементов списка. Для нахождения среднего достаточно сумму элементов спискаразделить на их количество.
avg(L,A):–
summa(L,S), % S - сумма элементов списка
length(L,K), % K - количество элементов списка
A=S/K. % A - среднее (отношение суммы
|
|
|
% к количеству)
Однако, если вызвать цель avg([],A) (найти среднее арифметическое пустого списка), то появится сообщение об ошибке "Division by zero" ("Деление на ноль"). Это произойдет, потому что предикат length([],K) конкретизирует переменную K нулем и при попытке достижения подцели A=S/K и происходит ошибка. Поэтому можно изменить этот предикат так, чтобы он работал и с пустым списком. Для этого добавим в процедуру, в виде факта, информацию о том, что среднее арифметическое элементов пустого списка равно нулю. И решение будет иметь вид
avg([],0):–!.
avg(L,A):–
summa(L,S),
length(L,K),
A=S/K.
ВНИМАНИЕ: при описании предиката avg в разделе PREDICATES второй аргумент будет не целого, а вещественного типа!
.
Пример 4.3. Создать предикат, находящий минимальный элемент списка.
Решение будет рекурсивным. Так как для пустого списка понятие минимального элемента не имеет смысла, то базис рекурсии запишем для одноэлементного списка. В одноэлементном списке минимальным элементом будет этот единственный элемент списка.
Шаг рекурсии: найдем минимум из первого элемента списка и минимального элемента хвоста.
min_list([X],X). % единственный элемент одноэлементного
% списка является минимальным элементом min_list([H|T],M):–
min_list(T,M_T), % M_T – минимальный элемент хвоста
min(H,M_T,M). % M – минимум из M_T и первого
% элемента исходного списка
ВНИМАНИЕ: в правиле, позволяющем осуществить шаг рекурсии, использован предикат min, который можно описать так:
min(X,Y,X):- X<Y,!.
min(_,Y,Y).
Модифицировав предикат min_list (подставив в правило вместо предиката min предикат max и поменяв его название), получим предикат, находящий не минимальный, а максимальный элемент списка.
Сортировка списков
Под сортировкой понимают расстановку элементов в некотором порядке. В дальнейшем будем упорядочивать элементы списков по неубыванию. Известны различные алгоритмы сортировки, которые можно разбить на два класса: сортировка данных, целиком расположенных в основной памяти (внутренняя сортировка), и сортировка файлов, хранящихся во внешней памяти (внешняя сортировка). Рассмотрим наиболее известные методы внутренней сортировки и реализуем их для сортировки списков в Прологе.
|
|
|
Пузырьковая сортировка
Идея метода: на каждом шаге сравниваются два соседних элемента списка. Если оказывается, что следующий элемент меньше предыдущий, то поменять их местами. Процесс продолжается до тех пор, пока есть пары соседних элементов, которые нужно поменять местами. Аналогия с пузырьком вызвана тем, что при каждом проходе минимальные элементы как бы "всплывают" к началу списка.
Реализуем пузырьковую сортировкупосредством двух предикатов. Предикат permutation будет сравнивать два первых элемента списка и в случае, если первый окажется больше второго, менять их местами. Если же первая пара расположена в правильном порядке, этот предикат будет переходить к рассмотрению хвоста. Предикат bubble будет осуществлять пузырьковую сортировкусписка, используя предикат permutation.
permutation([X,Y|T],[Y,X|T]):–
X>Y,!. % переставляем первые два элемента,
% если первый больше второго
permutation([X|T],[X|T1]):–
permutation(T,T1). % переход к перестановкам
% в хвосте
bubble(L,L1):–
permutation(L,LL), % предикат, осуществляющий
% перестановку
!,
bubble(LL,L1). % еще раз отсортировать
% полученный список
bubble(L,L). % если перестановок не было,
% то список отсортирован
Пузырьковый метод работает до тех пор, пока есть хотя бы пара элементов списка, расположенных в неправильном порядке. Как только такие элементы закончились, предикат permutation терпит неудачу, а bubble переходит от правила к факту и возвращает в качестве второго аргумента отсортированный список.
Сортировка вставкой
Данныйметод сортировки основан на том, что если хвост списка уже отсортирован, то достаточно поставить первый элемент списка на его место в хвосте, и весь список будет отсортирован. Для реализации этой идеи нужно создать два предиката. Предикат insert будет вставлять значение (голову исходного списка) в уже отсортированный список (хвост исходного списка), так чтобы он остался упорядоченным. Первым аргументом предиката insert будет вставляемое значение, вторым – отсортированный список, третьим – список, полученный вставкой первого аргумента в нужное место второго аргумента так, чтобы не нарушить порядок.
|
|
|
Предикат ins_sort организовывает сортировку исходного списка методом вставок. В качестве первого аргумента ему дают произвольный список, который нужно отсортировать. Вторым аргументом он возвращает список, состоящий из элементов исходного списка, стоящих в правильном порядке.
ins_sort([ ],[ ]). % Отсортированный пустой список
% остается пустым списком.
ins_sort([H|T],L):–
ins_sort(T,T_Sort), % T – хвост исходного списка,
% T_Sort – отсортированный
% хвост исходного списка.
insert(H,T_Sort,L). % Вставляем H (первый элемент
% исходного списка) в T_Sort,
% получаем список L (состоит
% из элементов исходного
% списка,стоящих по неубыванию)
insert(X,[],[X]). % При вставке любого значения
% в пустой список, получаем
% одноэлементный список.
insert(X,[H|T],[H|T1]):–
X>H,!, % Если вставляемое значение больше
% головы списка, значит его нужно
% вставлять в хвост.
insert(X,T,T1). % Вставляем X в хвост T,
% получаем список T1.
insert(X,T,[X|T]). % Это предложение (из-за отсечения
% в предыдущем правиле) выполнится,
% если вставляемое значение не
% больше головы списка T, то
% добавим его 1-м элементом в T.
Сортировка выбором
Идея этого способа сортировки: в списке найти минимальный элемент (используя предикат min_list). Удалить его из списка с помощью предиката delete_one (см. стр. 32). Оставшийся список отсортировать, приписывая минимальный элемент в качестве головы к отсортированному списку. Так как этот элемент был меньше всех элементов исходного списка, он будет меньше всех элементов отсортированного списка. Следовательно, если его поместить в голову отсортированного списка, то порядок не нарушится.
choice([ ],[ ]). % Отсортированный пустой список
% остается пустым списком.
choice(L,[X|T]):– % Приписываем X (мин. элемент
% списка L) к отсортированному
% списку T.
min_list(L,X), % X – минимальный элемент списка L
delete_one(X,L,L1), % L1 – результат удаления
% первого вхождения элемента
% X из списка L.
choice(L1,T). % Сортируем L1, результат – T.
|
|
|
Быстрая сортировка
Автором быстрой сортировкиявляется Чарльз Хоар. Идея метода: выбирается некоторый "барьерный" элемент, относительно которого исходный список разбивается на два подсписка. В один помещаются элементы, меньшие барьерного элемента, во второй – большие либо равные. Каждый из этих списков сортируется тем же способом, после чего приписываем к списку тех элементов, которые меньше барьерного, вначале сам барьерный элемент, а затем – список элементов не меньших барьерного. В итоге получается список, состоящий из элементов, стоящих в правильном порядке.
Для реализации использует предикаты partition и quick_sort.
Предикат partition — разбиение списка на два подсписка. Имеет четыре аргумента. Первые два элемента – входные: исходный список и барьерный элемент. Третий и четвертый элементы – выходные: список элементов исходного списка, которые меньше барьерного, и список, состоящий из элементов, которые не меньше барьерного элемента.
Предикат quick_sort — алгоритм быстрой сортировкиХоара. Состоит из двух предложений. Правило будет осуществлять с помощью предиката partition разделение непустого списка на два подсписка, затем сортировать каждый из этих подсписков рекурсивным вызовом себя самого. Затем, используя предикат append (см. стр. 29), конкретизировать второй аргумент списком, получаемым объединением отсортированного первого подсписка и списка, сконструированного из барьерного элемента (головы исходного списка) и отсортированного второго подсписка.
quick_sort([],[]). % отсортированный пустой список
% остается пустым списком
quick_sort([H|T],O):–
partition(T,H,L,G), % делим список T на L (список
% элементов, меньших барьерного
% элемента H) и G (список
% элементов, не меньших H).
quick_sort(L,L_s), % Список L_s – результат
% сортировки эл-тов списка L.
quick_sort(G,G_s), % Список G_s – результат
% сортировки эл-тов списка G.
append(L_s,[H|G_s],O). % Слияние списка L_s со
% списком, у которого H -голова
% G_s –хвост, О –результат.
partition([],_,[],[]). % Разделение пустого списка –
% пустые списки
partition([X|T],Y,[X|T1],Bs):–
X<Y,!, % Если элемент X меньше
partition(T,Y,T1,Bs). % барьерного элемента Y, то
% добавляем его в третий
% аргумент.
partition([X|T],Y,T1,[X|Bs]):–
partition(T,Y,T1,Bs). % Иначе – дописываем его
% в четвертый аргумент.
Пример 4.4. Пусть имеются два отсортированных списка, нужно объединить их элементы в один список так, чтобы объединенный список также остался отсортированным.
Идея решения: на каждом шаге сравнивать головы упорядоченных списков и ту из них, которая меньше, переписывать в результирующий список. И так до тех пор, пока один из списков не закончится. Когда один из списков опустеет, нужно дописать остатки непустого списка к уже построенному итогу.
|
|
|
Для решения создадим предикат fusion, реализующий приведенное описание. Так как не известно, какой из списков опустеет раньше, необходимо проводить рекурсию сразу по обоим базовым спискам. Создадим два факта – основания рекурсии: если соединяем некоторый список с пустым списком, то в итоге получим тот же самый список (случай, когда первый список пуст, и в случай, когда пуст второй список).
Шаг рекурсии дадут два правила: 1) если голова первого списка меньше головы второго списка, то голову первого списка и нужно дописать в качестве головы в результирующий список, после чего перейти к слиянию хвоста первого списка со вторым, а результат этого слияния будет хвостом итогового списка; 2) иначе, дописать голову второго списка в качестве головы результирующего списка, сливать первый список с хвостом второго списка.
fusion(L1,[],L1):–!. % при слиянии L1 с пустым
% списком получаем список L1,
fusion([],L2,L2):–!. % при слиянии пустого списка
% с L2 получаем список L2
fusion([H1|T1],[H2|T2],[H1|T]):–
H1<H2,!, % если голова 1-го списка H1
% меньше головы 2-го списка H2,
fusion(T1,[H2|T2],T). % сливаем хвост 1-го списка
% T1 со 2-ым списком [H2|T2] fusion(L1,[H2|T2],[H2|T]):–
fusion(L1,T2,T). % сливаем 1-ый список L1
% с хвостом 2-го списка T2
Сортировка слияниями
Сортировка слияниями предложена Джоном фон Нейманом в 1945 г. Идея метода: разбить список, который нужно упорядочить, на два подсписка; упорядочить каждый из них этим же методом, после чего слить упорядоченные подсписки обратно в один общий список.
Следовательно, сперва нужно создать предикат, который будет делить исходный список на два. Он будет состоять из двух фактов и правила. Первый факт будет утверждать, что пустой список можно разбить только на два пустых подсписка. Второй факт будет предлагать разбиение одноэлементного списка на тот же одноэлементный список и пустой список. Правило будет работать в случаях, не охваченных фактами, т. е. когда упорядочиваемый список содержит не менее двух элементов. В этой ситуации будем отправлять первый элемент списка в первый подсписок, второй элемент – во второй подсписок, и продолжать распределять элементы хвоста исходного списка..
splitting([],[],[]). % пустой список можно расщепить
% только на пустые подсписки
splitting([H],[H],[]). % 1-элементный список разбить
% на 1-элементный список
% и пустой список
splitting([H1,H2|T],[H1|T1],[H2|T2]):–
splitting(T,T1,T2). % элемент H1 отправить в
% 1-й подсписок, элемент H2 –
% во 2-й подсписок, хвост
% T разбить на подсписки T1,T2
Создадим предикат, который осуществляет сортировку списка. Он состоит из трех предложений: первое декларирует факт, что при сортировке пустого списка получается пустой список; второе утверждает, что одноэлементный список является упорядоченным; в третьем правиле — суть метода сортировки слиянием. Вначале список расщепляется на два подсписка с помощью предиката splitting, затем каждый из них сортируется рекурсивным вызовом предиката fusion_sort, и, используя предикат fusion, сливаем полученные упорядоченные подсписки в один список — результат упорядочивания элементов исходного списка..
fusion_sort([],[]):–!. % пустой список упорядочен
fusion_sort([H],[H]):–!. % 1-элементный список упорядочен
fusion_sort(L,L_s):–
splitting(L,L1,L2), % разделить L на два подсписка
fusion_sort(L1,L1_s), % L1_s – результат сортировки L1
fusion_sort(L2,L2_s), % L2_s – результат сортировки L2
fusion(L1_s,L2_s,L_s).% слить L1_s и L2_s в L_s
Этот алгоритм при прямом проходе дробит список на одноэлементные подсписки, после чего на обратном ходе рекурсии сливает их двухэлементные списки. На следующем этапе сливаются двухэлементные списки и т. д. На последнем шаге два подсписка сливаются в итоговый, отсортированный список.
Пример 4.5. Проверять, является ли список упорядоченным.
Для того чтобы список был упорядоченным, он должен быть либо пустым, либо одноэлементным, либо любые два его соседних элемента должны быть расположены в правильном порядке..
sorted([]). % пустой список отсортирован
sorted([_]). % 1-элементный список отсортирован
sorted([X,Y|T]):–
X<=Y, % список упорядочен, если первые два
sorted([Y|T]). % элемента расположены в правильном
% порядке и список, образованный
% вторым элементом и хвостом
% исходного, упорядочен
Варианты заданий
Проверить все алгоритмы сортировки с использованием Visual Prolog.
1. Модифицировать предикат, вычисляющий сумму элементов спискатак, чтобы он вычислял произведение элементов списка.
2. Модифицировать алгоритм сортировки выборомтак, чтобы он был основан на выборе максимального элемента списка и приписывании его в конец.
3. Изменить предикаты, реализующие алгоритм сортировки вставкой, чтобы список получился упорядоченным по невозрастанию.
4. Реализовать предикат avg без использования предикатов summa и length.
5. Изменить предикаты, реализующие алгоритм пузырьковой сортировки, чтобы в итоге список получился упорядоченным по невозрастанию.
6. Реализовать предикат min_list без использования предиката min.
7. Внести изменения в предикат choice, реализующий алгоритм сортировки выбором, чтобы он был основан на выборе максимального элемента списка и приписывании его в конец списка.
8. Дан список студентов группы (в произвольном порядке) вида «Фамилия_Имя» не менее 15 человек. Отсортировать его по алфавиту.
9. Дан список студентов группы (в произвольном порядке) вида «Фамилия_Имя» не менее 15 человек. Найти всех однофамильцев.
10. Дан список студентов группы (не менее 15 человек). Найти всех людей с одинаковым именем.
11. Пусть имеются три числовых списка. Найти наименьшее число в первом списке, наибольшее число во втором с среднее арифметическое в третьем.
12. Дан числовой список (в произвольном порядке) и пороговый параметр N. Разделить список на два: в первом – все числа меньше N, а во втором – больше.
13. Дан числовой список (в произвольном порядке) и пороговый параметр N. Разделить список на три: в первом – все числа меньше N/2, а во втором – от N/2 до 2*N, в третьем – больше 2*N.
14. Используя сортировку слияниями, упорядочить список от большего значения к меньшему.
15. Используя быструю сортировку, упорядочить список от большего значения к меньшему.
ЛАБОРАТОРНАЯ РАБОТА №5
МНОЖЕСТВА
Цель работы
Разработать инструментарий на Прологе, удобный для работы с элементами множеств.
|
|
|
