Информатика -продвинутый курс




ОБРАБОТКА СПИСКОВ


На практике часто встречаются задачи, связанные с перечислением объектов. В некоторых случаях при решении задач важно сохранять информацию об уже сделанных шагах решения, чтобы их не повторять. Для решения таких задач в языке Пролог предусмотрены списки.

Список можно задать перечислением элементов. Например, имена учеников класса:

[саша,петя,дима,ксюша,лена].

Элементами списка могут быть не только атомы, но и функции, и вообще любые элементы, даже списки. Заранее длина списка не задается, и в ходе выполнения программы она может меняться.

Альтернативный способ задания списка использует понятия головы и хвоста списка.

Например, в списке [X | Y] Х - это голова списка. Y - его хвост.

Хвост списка по определению также является списком.

Теперь список может быть определен рекурсивно:

1) пустой список [] - список:

2) [X | Y] - список, если Y - список.

Определение списка через его голову и хвост в сочетании с рекурсией лежит в основе большого числа программ, оперирующих списками. Эти программы состоят

1) из факта, ограничивающего рекурсию и описывающего операцию для пустого списка;

2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста ( в голове правила), через операцию над хвостом (в подцели).

Пример I:

определение числа элементов в списке.

Программа 122

сколько ([], 0).

сколько ([А|В], N) :- сколько (В, М), N is M+1.

?- сколько ([саша, игорь, лена]), X).

Ответ: Х=3.

Пример 2:

принадлежность элемента списку.

Программа 123

принадлежит (X, [X | Y]).

принадлежит (X, [A |Y ]) : - принадлежит (X,Y).

?-принадлежит (4,(1,3,4,9]).

Ответ:да.

Данная программа имеет очень простой декларативный смысл: элемент принадлежит списку, если он является его головой или принадлежит хвосту списка.

Пример 3:

соединение двух списков.

Эту задачу можно описать с помощью следующих предикатов:

а) ограничение рекурсии состоит в том, что если к пустому списку [ ] добавить список Р, то в результате получится Р;




Содержание  Назад  Вперед