Лабораторная работа № 3. Обработка списков в Прологе

Цель работы:освоение программирования на языке Пролог с использованием списков.

Рекомендации по выполнению работы

В Прологе нет такой распространенной и часто используемой структуры хранения данных как массивы, но зато есть развитые возможности работы со списками. Список – упорядоченный набор элементов одного типа. В отличие от массивов, количество элементов которых строго фиксировано (в большинстве языков программирования), списки позволяют модифицировать, добавлять или удалять из него элементы.

Списки в Прологе заключаются в квадратные скобки, например [1, 2, 8, 123] или ['Пн', 'Вт', 'Четверг']. Список [ ], не содержащий ни одного элемента, называется пустым. Каждый непустой список состоит из двух частей: головы и хвоста. Головой является первый элемент списка, хвостом – все остальное.

Таблица 3

Списки и их составные части

Список	Голова	Хвост
[1, 2, 8, 123]		[2, 8, 123]
['Пн', 'Вт', 'Четверг']	'Пн'	['Вт', 'Четверг']
[1.25]	1.25	[]
[]	не определена	не определен

В программе голова отделяется от хвоста символом «|».

Часто используемыми операциями при работе со списками являются:

· добавление элемента в список;

· проверка наличия элемента в списке;

· объединение списков;

· удаление элемента из списка;

· задание обратного порядка следования элементов списка;

· разделение списка на два.

Программный код и примеры вопросов, содержащие предикаты для работы со списками, показаны на рис.7.

Для операции добавления элемента в список не требуется отдельного правила, если этот элемент добавляется в начало списка (см. вопрос 1 на рис. 7). Для остальных операций требуется определение отдельных предикатов, в т. ч. содержащих рекурсивные правила.

Рис. 7. Предикаты обработки списков

Задание на выполнение работы

Разработать программу с использованием списков, отвечающую следующим требованиям.

A.По индивидуальному заданию добавить в программу правила для решения задачи.

1. Даны два списка целых чисел A₁, A₂, ..., A_n и B₁, B₂, ..., B_n. Объединить эти списки в один, исключить все повторения чисел и упорядочить их по возрастанию.

2. В списке целых чисел S₁, S₂, ..., S_n исключить все последовательности указанного вида, например [1, 11, 24, 5].

3. В списке символов S₁, S₂, ..., S_n найти первое и последнее вхождения указанного символа и исключить все символы между ними.

4. В списке символов S₁, S₂, ..., S_n найти длину наибольшей последовательности, построенной повторением одного и того же символа.

5. В списке символов S₁, S₂, ..., S_n каждую указанную последовательность символов заменить на другую указанную последовательность.

6. В списке символов S₁, S₂, ..., S_n найти самое короткое слово, если разделителем между словами является один или несколько пробелов и удалить его.

7. В списке символов S₁, S₂, ..., S_n найти самое длинное слово, если разделителем между словами является один или несколько пробелов и удалить его.

8. В списке символов S₁, S₂, ..., S_n найти все вхождения указанного слова, если разделителем между словами является один или несколько пробелов.

9. В списке символов S₁, S₂, ..., S_n найти число слов с одинаковыми первой и последней буквами, если разделителем между словами является один или несколько пробелов. Определить самое длинное такое слово.

10. В списке символов S₁, S₂, ..., S_n найти среднюю длину слов, если разделителем между словами является один или несколько пробелов. Определить все слова, имеющие эту длину.

11. Преобразовать список целых чисел A₁, A₂, ..., A_n следующим образом: исключить нули, слева записать все положительные числа, справа - все отрицательные.

12. Преобразовать список целых чисел A₁, A₂, ..., A_n следующим образом: исключить нули, слева записать все четные числа, справа – все нечетные.

13. Преобразовать список целых чисел A₁, A₂, ..., A_n следующим образом: исключить нули, слева записать все простые числа, справа – все составные.

14. В списке целых чисел A₁, A₂, ..., A_n определить максимально длинную последовательность чисел, расположенных в возрастающем порядке.

15. В списке целых чисел A₁, A₂, ..., A_n определить максимально длинную последовательность чисел, расположенных в убывающем порядке.

16. Список целых чисел A₁, A₂, ..., A_n оставить без изменений, если он упорядочен по возрастанию или убыванию. В противном случае: каждый четный элемент списка утроить, каждый элемент, стоящий на нечетном месте и кратный четырем, удалить.

Б.Отчет должен содержать:

· титульный лист;

· описание задания;

· текст программы;

· вопросы с ответами, иллюстрирующие корректность работы программы;

· вывод.

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

1. Дайте определение понятий: «терм», «предикат», «формула».

2. Назовите кванторы переменных и особенности их применения.

3. Назовите язык программирования, реализующий логику предикатов первого порядка.

4. Перечислите и дайте характеристику разновидностей предложений в Прологе.

5. Какие символы используются в Прологе для обозначения логи­чес­ких операций «И», «ИЛИ» и «импликации»?

6. Что такое «фраза Хорна»?

7. Дайте определение понятий: «свободная переменная», «связанная пе­ре­менная», «анонимная переменная».

8. Какой метод используется в Прологе для поиска решения (дока­за­тельства цели)?

9. Что понимается под рекурсией в программировании?

10. Что понимается под «головой» и «хвостом» списка?

ОНТОЛОГИИ