1. Написать программу нахождения последнего элемента списка. Для нахождения последнего элемента списка используйте двунарный предикат last(type_of_elements, list). Первый аргумент этого предиката задает последний элемент списка, второй – список, в котором производится поиск последнего элемента. Т. о. цель last(X, L) согласуется с базой данных, если элемент X является последним элементом списка L.
Например:
?- last(3, [1, 2, 3])
Yes
?- last(X, [1, 2, 3])
2. Написать программу исключения первого вхождения элемента в список. Для исключения первого вхождения некоторого элемента в список используйте предикат exclude(type_of_elements, list, list). Цель exclude(X, Y, Z) исключает первое вхождение элемента X в список Y, формируя новый список Z.
Например:
?- exclude(2, [1, 2, 3, 2], Z)
Z=[1, 3, 2]
3. Написать программу обращения списка. Обращенный список можно получить путем присоединения головы этого списка к обращенному хвосту. Для решения задачи используйте двунарный предикат reverse(list, list). Первый аргумент этого предиката задает начальный список, второй – обращенный.
Например:
?- reverse([1, 2, 3], Y)
Y=[3, 2, 1]
4. Написать программу поиска минимального элемента списка и его порядкового номера в этом списке. Для решения задачи используйте тринарный предикат minimum(type_of_elements, integer, list). Первый аргумент в этом предикате задает минимальный элемент списка, второй – индекс этого элемента в списке, третий – список, в котором производится поиск минимального элемента. Т. о. цель minimum(X, N, L) согласуется с базой данных, если X является минимальным элементом списка L, а N – порядковый номер элемента X в этом списке.
Например:
?- minimum(1, 4, [2, 5, 3, 1, 7])
Yes
?- minimum(X, N, [2, 5, 3, 1, 7])
X=1, N=4
5. Написать программу сортировки элементов списка с помощью прямого включения. При сортировке включением каждый элемент списка рассматривается отдельно и включается в новый список на соответствующее место. Алгоритм этой сортировки следующий:
FOR i:= 2 TO n DO
x:= a[i];
включение x на соответствующее место среди
a[1]... a[i]
END
Пример сортировки списка с помощью прямого включения:
начальный список 44 55 12 42
i = 2 44 55 12 42
i = 3 12 44 55 42
i = 4 12 42 44 55
Для решения задачи используйте двунарный предикат insertion_sort(list, list). Первый аргумент в этом предикате задает начальный список, второй – отсортированный.
Например:
?- insertion_sort([2, 5, 3, 1, 7], Y)
Y=[1, 2, 3, 5, 7]
Контрольные вопросы
1. Реализуйте на языке Пролог алгоритмы прохождения бинарных деревьев в прямом и обратном порядке.
2. В результате выполнения целевого утверждения find(X, [1, 2, 3]) переменная X примет следующие значения:
X=1
X=2
X=3
Если поменять местами правила для предиката find следующим образом:
‚ find(Elem, [_|Tail]):-find(Elem, Tail).
find(Elem, [Elem|_]).
то в результате выполнения целевого утверждения find(X, [1, 2, 3]) переменная X примет следующие значения:
X=3
X=2
X=1
Объясните, почему изменился порядок нахождения решений.
3. Реализуйте на языке Пролог алгоритм слияния двух отсортированных списков.
4. Реализуйте на языке Пролог рекурсивный и итерационный алгоритмы определения длины списка.
5. Дан плоский замкнутый многоугольник {P1, P2,..., Pn}. Требуется найти площадь ориентированного многоугольника. Площадь вычисляется с помощью линейного интеграла 1/2 ò xdy – ydx, где интегрирование производится по границе многоугольника. Решением данной задачи является приведенная ниже программа, задающая отношение area(Chain, Area). Chain является списком координат вершин. Значением переменной Area будет площадь многоугольника с данными вершинами.
area([Tuple], 0).
area([(X1, Y1), (X2, Y2)|XYs], Area):-
area([(X2, Y2)|XYs], Area1),
Area=(X1*Y2-Y1*X2)/2+Area1.
Площадь положительна, если многоугольник обходится против часовой стрелки, и отрицательна в противном случае.
Перепишите приведенную выше программу так, чтобы она стала итерационной.
Лабораторная работа №4
Знакомство с языком списочных структур Лисп
