3.4 Задание на лабораторную работу

1. Написать программу нахождения последнего элемента списка. Для нахождения последнего элемента списка используйте двунарный предикат last(type_of_elements, list). Первый аргумент этого предиката задает последний элемент списка, второй – список, в котором производится поиск последнего элемента. Т. о. цель last(X, L) согласуется с базой данных, если элемент X является последним элементом списка L.

Например:

?- last(3, [1, 2, 3])

Yes

?- last(X, [1, 2, 3])

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]

3.5 Контрольные вопросы

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. Дан плоский замкнутый многоугольник {P₁, P₂, ..., P_n}. Требуется найти площадь ориентированного многоугольника. Площадь вычисляется с помощью линейного интеграла 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.

Площадь положительна, если многоугольник обходится против часовой стрелки, и отрицательна в противном случае.

Перепишите приведенную выше программу так, чтобы она стала итерационной.