Предикат одержання елемента по номеру у списку

Предикат перевірки, чи є список паліндромом.

Обернення списку.

Видалення зі списку повторюваних елементів.

Аргументами предиката unіk є два списки: вихідний і результуючий. Зміст алгоритму простий: якщо елемент присутній у списку (перевіряється предикатом member), то він не записується в результуючий список, інакше додається як головний елемент.

unіk([ ],[ ]).

unіk([H|T], L):- member(H,T), unіk(T,L).

unіk([H|T], [H|L]):- unіk(T,L).

reverse(L1,L2).

Аргументи L1 і L2 - два списки, список L2 містить елементи списку L1, записані у зворотному порядку.

Для рішення цієї задачі скористаємось рекурсією. Базис: якщо записати елементи порожнього списку (яких немає) у зворотному порядку - знову одержимо порожній список. Крок рекурсії: щоб одержати "перевернений" список, можна "перевернути" його хвіст й "приклеїти" до нього перший елемент вихідного списку. Запишемо це.

reverse([ ],[ ]). /* обернення порожнього списку дає

порожній список*/

reverse([X|T],Z):- reverse(T,S), conc(S,[X],Z).

/* обертаємо хвіст і приписуємо до нього

праворуч перший елемент вихідного списку*/

Зверніть увагу, що другим аргументом у предикаті conc повинен стояти саме одноелементний список [X], а не елемент X. Це пов'язане з тим, що аргументами предиката conc повинні бути списки.

Можна написати даний предикат без використання предиката conc. Правда, тоді доведеться додати аргумент, у якому буде "накопичуватись" результат.

reverse(L1,L2):-reverse1(L1,[],L2).

reverse1([],L,L).

reverse1([H|T],L1,L2):-reverse1(T,[H|L1],L2).

Предикат reverse у цьому випадку є інтерфейсним, він запускає в роботу основний робочий предикат reverse1, що має додатковий другий аргумент - список, що спочатку порожній і використається для обернення списку. На кожному кроці рекурсії один елемент вихідного списку стає головою проміжного списку. Третій аргумент передається від кроку до кроку й конкретизується в момент досягнення базового стану предиката reverse1. Коли перший список вичерпаний, другий уже містить елементи, записані у зворотному порядку. Зазначимо, що наявність третього аргументу, що фіксує результат, обов'язкова, тому що після зворотного проходження рекурсії всі конкретизовані змінні приймають свої первісні значення.

Паліндромом є список, що збігається зі своїм оберненням. У цього предиката буде всього один аргумент - список, що перевіряється на "паліндромність".

Очевидне рішення – використати предикат обернення списку: перевернути список і перевірити, чи збігається результат з вихідним списком:

palіndrom(L):-

reverse (L,L).

Це схоже на одержання елемента по його номеру у масиві в імперативних мовах програмування. Предикат буде трьох аргументний: перший аргумент - вихідний список, другий аргумент - номер елемента і третій - елемент списку.

Рішення проведемо рекурсією по номеру елемента. За базис приймемо факт, що першим елементом списку є його голова. Крок рекурсії полягає у припущенні, що N-й елемент списку є (N-1)-м елементом хвоста:

n_element([X|_],1,X).

n_element([_|L],N,Y):-

N1=N-1,

n_element(L,N1,Y).

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