Т е м а: Використання списків структур

М е т а: Навчитись описувати та використовувати для розв’язування задач списки, елементами яких є структури.

З а в д а н н я:

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)

б) Описати відношення 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. В якій мірі відсік є аналогом розгалуження в мовах процедурного типу?