Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задание на лабораторную работу. 1. Написать программу нахождения последнего элемента списка




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

Знакомство с языком списочных структур Лисп







Дата добавления: 2015-08-17; просмотров: 105. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.005 сек.) русская версия | украинская версия