Поиск заданного элемента

Объединение списков.

Генерирование списка из (N2-N1) последовательных целых чисел, начиная с N1.

Для формирования списка создадим отношение genlist(N1, N2, L), где

N1 – начальный элемент списка

N2 – его верхняя граница

L – список

Возможны случаи:

1) если N1 = N2, тогда N1 – не добавляется в список и L – пустой список.

genlist (N2, N2, [ ]) – первая часть правила (условие останова).

2) если N1 < N2, то N1 помещаем в голову списка, затем увеличиваем N1 на 1 и для нового значения снова вызывается genlist. Получаем вторую часть правила:

genlist (N1, N2, [N1 | L]): - N1 < N2, N = N1+1, genlist (N, N2, L).

Таким образом, правило формирования списка имеет вид:

genlist (N2, N2, [ ]). % нерекурсивная часть правила

genlist (N1, N2, [N1 | L]): - % рекурсивная часть правила

N1 < N2, N = N1+1, GenList (N, N2, L).

Например, для формирования списка [2, 3, 4, 5] следует указать запрос:

GOAL

GenList (2, 6, L), Write (L), nl.

Создадим отношение append(L1, L2, L3), где L1, L2 – исходные списки, L3 – список, полученный в результате присоединения L2 к L1.

Возможны случаи:

1) если L1 пустой список, то результирующий список L3 равен списку L2. Получаем первую (нерекурсивную) часть правила:

append ([ ], L, L).

2) если L1 не пустой список, то делим его на голову и хвост ([X | L1]). Вторая (рекурсивная) часть правила:

append ([X | L1], L2, [X | L3]): - append (L1, L2, L3).

Таким образом, правило объединения списков имеет вид:

append ([ ], L, L).

append ([X | L1], L2, [X | L3]): - append (L1, L2, L3).

Например, для объединения списков [1, 2, 3] и [4, 5] следует написать запрос:

GOAL

append ([1, 2, 3], [4, 5], L) write [L].

Результат:

[1, 2, 3, 4, 5]

При выполнении программы из L1 выделяется и заносится в стек по одному элементу (голова списка) до тех пор, пока L1 не станет пустым. После этого выполняется первая часть правила и L3 получает значение L2, то есть L3 = [4, 5] начинается выгрузка элементов из стека и добавление их в голову L3.

Правило append обладает большое гибкостью и позволяет решать множество задач по обработке списка. Его можно использовать для решения обратной задачи: разбиение исходного списка на две части.

Например, чтобы определить все возможные способы разбиения списка [1,2,3], следует составить запрос:

GOAL

append (L1, L2, [1,2,3]), write (“L1=”, L1, “L2=”, L2), fail, nl.

Результат:

L1 = [ ] L2 = [1, 2, 3]

L1 = [1] L2 = [2, 3]

L1 = [1, 2] L2 = [3]

L1 = [1, 2, 3] L2 = [ ]

Чтобы определить содержится ли элемент X в списке L создадим отношение member(X, L).

Возможны случаи:

1) если X совпадает с головой списка L, то элемент найден и поиск прекращается. Первая часть правила (нерекурсивная):

member (X, [X | L]).

2) если X не принадлежит голове, то он может принадлежать хвосту. Отбрасываем голову списка и вызываем правило для оставшегося списка. Вторая часть правила (рекурсивная):

member (X, [_ | L]: - member (X, L).

Таким образом, правило поиска элемента имеет вид:

member (X, [X | L]).

member (X, [_ | L]: - member (X, L).

Например, для ответа на вопрос «Содержится ли число 4 в списке [2, 3, 4, 5]?», можно составить запрос:

GOAL

member(4, [2, 3, 4, 5]),Write (“yes”);Write (“no”), nl.

При выполнении поиска X сравнивается с головой L. Если элементы не совпадают, то первый элемент отбрасывается и X сравнивается с головой полученного списка и так далее, пока L не станет пустым списком. Если элемент X найден, то цель достигнута, выводится сообщение “yes”, иначе выводится “no”.

Дата добавления: 2014-01-05