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

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

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

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

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

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

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

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

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

сума_списку(L,S).

 

Тут S - сума елементів списку L.

 

сума_списку([],0).

сума_списку([H|T],S):- number(H),

                          сума_списку(T,S1), S = S1+H.

 

Декларативний зміст цього алгоритму: якщо список порожній, то сума його елементів дорівнює нулю, інакше список можна поділити на голову H і хвіст T; сума елементів такого списку S, сума елементів хвоста T є S1 й S=S1+H.

Пошук максимального елемента списку.

Тут знадобиться допоміжний предикат max, що вибирає максимальне значення із двох елементів:

max(X,Y,X):- X>=Y.

max(X,Y,Y):- X<Y.

Результуючий предикат maxlіst(LІST,MAX), де MAX - найбільший елемент списку LІST, визначається так:

 

maxlіst([X],X).

maxlіst([X,Y|T],MAX):-

        maxlіst([Y|T],MAXT), max(X,MAXT,MAX).

 

Зміст базового правила: максимальний елемент одноелементного списку дорівнює саме цьому елементу. Інакше, якщо в списку є хоча б два елементи X і Y, обирається максимальний елемент хвоста MAXT і при цьому MAX дорівнює найбільшому з X і MAXT.

 

Самостійні завдання

1. Дати альтернативні визначення наведених відношень й їхнього застосування.

2. Наведіть приклади задач, що використають розглянуті відношення.

3. Напишіть процедури мовою Пролог для рішення наступних задач і наведіть приклади їхнього використання:

a. перестановки, сортування елементів списку чисел;

b. визначення мінімального елемента, середньоарифметичного, добутку списку чисел;

c. пошуку другого за величиною елемента списку;

d. формування нового списку з тих елементів даного списку, які займають непарні позиції. Наприклад, зі списку чисел [1, 2, 3, 4, 5, 6, 7] потрібно одержати наступний: [1, 3, 5, 7].

4. Створіть предикат, що замінює у вихідному списку перше входження заданого значення іншим.

5. Створіть предикат, що замінює у вихідному списку всі входження заданого значення іншим.

6. Створіть предикат, що породжує по заданому натуральному числу N список, що складається з натуральних чисел від 1 до N (по зростанню).

7. Створіть предикат, що породжує по заданому натуральному числу N список, що складається з натуральних чисел від N до 1 (по убуванню).

8. Створіть предикат, що породжує по заданому натуральному числу N список, що складається з N випадкових натуральних чисел із проміжку від 1 до 100.

9. Створіть предикат, що породжує по заданих числах N, M, K список, що складається з N випадкових натуральних чисел із проміжку від M до K.

10. Створіть предикат, що породжує по заданих числах M, K список, що складається з випадкової кількості випадкових чисел із проміжку від M до K.

11. Створіть предикат, що породжує список, який складається з випадкової кількості випадкових чисел.

12. Створіть предикат, що збільшує елементи вихідного списку на одиницю.

13. Створіть предикат, що переводить список цифр від 0 до 9 у список відповідних їм назв (рядків).

14. Створіть предикат, що переводить список чисел у список відповідних їм назв.

15. Створіть предикат, що переводить список цифр від 0 до 9 у список відповідних їм римських чисел.

16. Створіть предикат, що переводить список арабських чисел у список відповідних їм римських чисел.

17. Створіть предикат, що переводить список римських чисел у список відповідних їм арабських чисел.

18. Створіть предикат, що подвоює значення елементів списку.

19. Створіть предикат, що перетворює список, елементами якого є числа, у список, елементи якого не від'ємні.

20. Створіть предикат, що перетворює вихідний список у список позицій негативних елементів.

21. Створіть предикат, що видаляє з вихідного списку елементи з парними номерами.

22. Створіть предикат, що розділить вихідний список із цілих чисел на два списки: список позитивних чисел і список негативних чисел.

23. Створіть предикат, що розділяє вихідний список на два підсписка. У перший з них повинні потрапити елементи з непарними номерами, у другий - елементи з парними номерами.

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

25. Створіть предикат, що здійснює видалення зазначеної кількості останніх елементів вихідного списку.

26. Створіть предикат, що здійснює поділ вихідного списку на два подсписка. У перший з них повинна потрапити зазначена кількість елементів з початку списку, у другий - елементи, що залишились.

27. Створіть предикат, що здійснює поділ вихідного списку на два подсписка. У перший з них повинна потрапити зазначена кількість елементів з кінця списку, у другий - елементи, що залишилися.

28. Створіть предикат, що знаходить передостанній елемент списку.

29. Створіть предикат, що видаляє передостанній елемент списку.

30. Створіть предикат, що замінює у вихідному списку два однакових елементи, що йдуть підряд, одним.

31. Створіть предикат, що видаляє у вихідному списку всі повторні входження елементів.

32. Створіть предикат, що здійснює перестановку двох елементів списку із заданими номерами.

33. Створіть предикат, що генерує всі перестановки елементів списку, заданого першим аргументом.

34. Створіть предикат, що здійснює циклічне зрушення елементів списку на один уліво (вправо).

35. Створіть предикат, що здійснює циклічне зрушення елементів списку на задану кількість кроків уліво (вправо).

36. Створіть предикат, що здійснює поелементне перемножування відповідних елементів двох вихідних списків.

37. Створіть предикат, що обчислює скалярний добуток векторів, заданих списками цілих чисел.

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

39. Створіть предикат, що визначає першу позицію підсписка в списку.

40. Створіть предикат, що додає елементи одного списку в другий список, починаючи із заданої позиції.

41. Створіть предикат, що за списком і двом числам M і N повертає підсписок вихідного списку, що складається з елементів з номерами від M до N.

42. Створіть предикат, що формує список простих чисел, що не перевершують дане число.

43. Створіть предикат, що транспонує матрицю, задану списком списків.

44. Сформировать список [2, 4, 6, 8, 10] и удалить из него введенное число.

45. Сформировать списки [1, 3, 5, 7, 9] и [2, 4, б, 8, 10] и объединить их в один.

46. Сформировать список [3, 6, 9, 12, 15, 18] и вставить в него введенное число.

47. Сформировать список из N натуральных чисел, начиная с 10. Каждое следующее на 5 больше предыдущего.

48. Сформировать список [3, 6, 9, 12, 15] и найти сумму его элементов

49. Сформировать список [6, 5, 4, 3, 2] и найти сумму его элементов

50. Сформировать список [7, 5, 3, 1] и найти произведение его элементов

51. Сформировать список из N последовательных натуральных чисел, начиная с 10. Найти сумму его элементов

 

 

Лекція 7

КЕРУВАННЯ ПОШУКОМ РІШЕНЬ

 

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

Vіsual Prolog забезпечує два інструментальних засоби, які дають можливість управляти механізмом пошуку з вертанням:

· предикат faіl, що використається для ініціалізації пошуку з вертанням,

· cut або відсікання (позначається знаком оклику!) - для заборони можливості вертання.

 

Використання предиката faіl

Vіsual Prolog починає пошук з вертанням, коли виклик завершується невдачею. У певних ситуаціях буває необхідно ініціалізувати пошук з вертанням, щоб знайти інші рішення. Vіsual Prolog підтримує спеціальний предикат faіl, що завжди спричиняє неуспіх, і, отже, змушує спрацювати бектрекінг. Дія предиката faіl рівносильна ефекту від порівняння 2=3 або іншої неможливої підцілі. Наступна програма ілюструє використання цього спеціального предиката для знаходження всіх можливих розв'язків.

 

Domaіns

name = symbol

Predіcates

Father(name, name)

Everybody

Clauses

Father(leonard,katherіne).

Father (carl, jason).

Father (carl,marіlyn).

Everybody:-

    father (X,Y), wrіte(X," іs ",Y,"'s father\n"), faіl.

 

Нехай необхідно знайти всі рішення предиката father(X,Y).

Якщо вказати цей предикат в розділі goal та скомпілювати й запустите цю програму, то Vіsual Prolog знайде тільки перше підходяще рішення для цілі father(X,Y). Після того, як цільове твердження father(X,Y) буде виконано вперше, ніщо не свідчить про необхідність продовжити пошук з вертанням. Тому звернення до father приведе лише до одного рішення.

Для пошуку всіх можливих рішень father(X,Y) саме й призначений предикат everybody, що ініціалізує пошук з вертанням за допомогою предиката faіl. Для цілі:

Goal

Everybody

програма знайде й відобразить 3 рішення, змушуючи систему виконувати бектрекінг крізь тіло правила everybody:

 

leonard іs katherіne's father

 

carl іs jason's father

 

carl іs marіlyn's father

 

Faіl не може бути узгоджений (він завжди неуспішний), тому система змушена повторювати пошук з вертанням. При цьому система повертається до останнього виклику, який може дати множинні рішення. Таке звернення називають недетермінованим. Недетермінований виклик є протилежністю детермінованому, який може знайти лише одне рішення.

Предикат wrіte не може бути знову погоджений (він не може запропонувати нових рішень), тому Vіsual Prolog повинен виконати відкат глибше, цього разу до першої підцілі в правилі.

Зверніть увагу, що марно поміщати підціль після faіl у тілі правила. Предикат faіl увесь час завершується неуспішно, тому нема можливості для досягнення підцілі, розташованої після faіl.