Т е м а: Використання списків структур
М е т а: Навчитись описувати та використовувати для розв’язування задач списки, елементами яких є структури.
З а в д а н н я:
1. Виконати запропоновані Вам програми для задачі про розташування восьми ферзів на шаховій дошці та для задачі про додавання двох многочленів. Проаналізуйте рекурсивні правила, які використовуються в цих програмах.
2. Нехай поля шахової дошки подані парами координат у вигляді p(X,Y), де X, Y набувають значень від 1 до 8.
а) Визначити відношення step_hourse(P1,P2), яке відповідає ходу коня на шаховій дошці з поля P1 в поле P2. Вважайте, що поле P1 завжди задано, а поле P2 може бути не конкретизованим. Наприклад,
?– step_hourse(p(1,1),P).
P=p(3,2);
P=p(2,3)
no
б) Описати відношення path_horse(Path,N), де Path — список перших N полів, на які послідовно може ходити кінь згідно правил гри по порожній дошці. Перше поле в шляхові Path задано. Використовуючи відношення path_horse, написати запит для знаходження довільного шляху, який складається із чотирьох ходів і розпочинається з поля p(2,1), а закінчується на протилежній стороні дошки (Y=8). Цей шлях після другого ходу повинен ще проходити через поле P(5,4).
В к а з і в к и до виконання завдань: У завданні 1 для задачі про додавання многочленів попробуйте різні варіанти запитів, які відповідають різним співвідношенням між степенями многочленів.
Під час апробації процедури для предикати path_horse обмежте довжину шляху коня невеликою початковою кількістю ходів, інакше отримаєте повідомлення про переповнення рекурсивного стеку.
К о н т р о л ь н і п и т а н н я:
1. Навести приклади опису списків структур в мові Turbo-Prolog.
2. Для чого в рекурсивних процедурах потрібно описувати граничні умови?
Лабораторна робота № 7 (4 год)
Т е м а: Керування механізмом перебору в Prolog–системах за допомогою відсіку.
М е т а: Оволодіти прийомами використання відсіку в Пролог–програмах.
З а в д а н н я:
1. Наступне відношення розподіляє числа на три класи — додатні, нуль та від’ємні:
class(Number, positive):–Number>0.
class(Number, zero):–Number=0.
class(Number, negative):–Number<0.
Зробити цю процедуру більш ефективною за допомогою відсіку.
2. Описати процедуру devide(Numbers,Positive,Negative), яка розбиває список чисел на два списки: Список, який містить невід’ємні числа, та список від’ємних чисел. Наприклад,
devide([3,-1,0,5,-2],[3,0,5],[-1,-2])
Складіть два варіанти цієї процедури: один з використанням відсіку, другий — без нього.
3. Описати відношення, за допомогою якого можна здійснювати віднімання множин:
difference(Set1, Set2, Diff)
де всі три множини подаються у вигляді списків. Нариклад,
difference([a,b,c,d], [b,d,e,f], [a,c])
4. Написати процедуру un(L1,L2,L) злиття двох впорядкованих списків L1 і L2 у третій список L. Наприклад,
?- un([2,5,6,6,8],[1,3,5,9],L)
L=[1,2,3,5,5,6,6,8,9]
К о н т р о л ь н і п и т а н н я:
1. Як можна обмежити ті розгалуження в рекурсивних алгоритмах, на яких завідомо не можна отримати відповіді розв’язуваної задачі?
2. В якій мірі відсік є аналогом розгалуження в мовах процедурного типу?
3. Як в мові Пролог вводиться в розгляд поняття заперечення?
Лабораторна робота № 8 (2 год)