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

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).

Видалення зі списку всіх входжень заданого значення.

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

Без рекурсії не обійдеться й цього разу.

Базис рекурсії: є той факт, що видалення довільного елементу з порожнього списку дає порожній список.

Крок рекурсії заснований на тім, що:

§ якщо перший елемент списку є видаляємим, то потрібно перейти до видалення заданого значення із хвоста списку. Результатом цього повинен стати список, отриманий шляхом видалення всіх входжень шуканого значення із хвоста первісного списку;

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

delete_all(_,[],[]).

delete_all(X,[X|L],L1):- delete_all(X,L,L1).

delete_all(X,[Y|L],[Y|L1]):- X<>Y, delete_all(X,L,L1).

Якщо нам потрібно видалити не всі входження певного значення в список, а тільки перше, то варто небагато змінити вищеописану процедуру. Це можна зробити декількома способами. Розглянемо один з них.

В першому правилі рекурсивний виклик замінимо предикатом відсіканням. У цьому випадку, поки перший елемент списку не виявиться видаляємим, будемо переходити до розгляду хвоста.

delete_one(_,[],[]).

delete_one(X,[X|L],L):-!.

delete_one(X,[Y|L],[Y|L1]):- delete_one(X,L,L1).

Обчислення суми елементів списку

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