Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Загальна структура програм на мові TURBO-PROLOG
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Методичні вказівки
Предмет:
Логічне програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти України
Державний університет “Львівська політехніка”
Кафедра АСУ
Методичні вказівки до курсу лабораторних робіт
для студентів базового напрямку
“Комп'ютерні науки”
з дисципліни
“ЛОГІЧНЕ ПРОГРАМУВАННЯ”
Львів 2010
Укладачі: Зербіно Дмитро Дмитрович, Різник Олег Яремович
Консультант: Вальковський Володимир Олександрович
Лабораторна робота 1
Тема: Загальна структура програм на мові TURBO-PROLOG.
Мета роботи: Зрозуміти принцип логічного програмування.
Завдання: Написати програму, яка складає таблицю істин-
ності деякої логічної функції, заданої схемою
з елементів “І-НЕ”
Роз'яснення до завдання.
Програма на мові логічного програмування не задає алгоритм обробки даних. Вона декларує логічні зв'язки між деякими подіями, властивостями, об'єктами, діями. Зв'язок представляється як предикат, який містить вказані логічні поняття: події властивості, об'єкти, дії у вигляді своїх змінних. Наприклад, X=Y+Z можна розглядати як предикат, в якому права частина відома, а ліва - не відома. Тоді, для істинності предиката необхідно прирівняти праву і ліву частини рівняння. Якщо відомі обидві частини рівняння, то цей предикат можна трактувати як логічну умову, яка може бути істиною. Сам предикат також має чітке логічне визначення в абстрактних поняттях тих змінних, з якими він оперує. В даному прикладі, цей предикат можна назвати “додавання двох змінних”.
Логічні умови, які накладаються на змінні в тілі предикату визначають його істинність. Програма є просто множиною предикатів, які посилаються один на одний і всі вони закінчуються крапкою. Кожен з них в залежності від того, які змінні визначені, а які - ні, можна трактувати так:
Якщо відомі X, Y, Z,... то чи виникне подія f(X,Y,Z,...)? (або чи збережеться властивість f(X,Y,Z,...)?, або чи існуватиме об'єкт f(X,Y,Z,...)? і т.д.)
Якщо відомо, що подія f(X,Y,Z,...) відбулася (або є властивість f(X,Y,Z,...), або якщо об'єкт f(X,Y,Z,...) існує), то якими повинні бути X, Y, Z,... ? Звичайно, розв'язок системи предикатних рівнянь може існувати, і вбудований механізм інтерпретації логічних програм його знайде, але під час програмування краще про нього не думати.
Фактично, програма складається з множини розділів, а кожний розділ складається з множини визначень, характерних для даного розділу. Якщо програма немає інших розділів крім “goal”, то її виконання не відрізняється від звичайного лінійного алгоритму, наприклад:
goal X=5, Y=6, Z=X+Y, write(“ Z=“,Z).
Отже, в “goal” задається мета програми - обчислити деякий предикат. В розділі “clauses” задається логічна модель задачі, яка складається з фактів і правил. Кожний факт має відповідну логічну інтерпретацію в поняттях, на яких базується модель задачі. Правило фактично задає опис алгоритму вирішення задачі у вигляді переліку інших простіших задач, які необхідно розв'язати.
При складанні програми на декларативній мові, такій як PROLOG, існує два шляхи. Перший - це взагалі забороняється конкретне алгоритмічне мислення, яке заважає помітити логічні зв'язки і сформулювати визначення у вигляді правил. Коректність програми повинна повністю забезпечуватись правильними визначеннями логічних понять та предикатів, з якими працює програма. Наведемо приклад програми для знаходження кращого ходу для гри в “сірники” (подивіться текст програми).
Умова гри: на столі знаходиться N сірників. Кожен з гравців може брати 1, 2 чи 4 сірника з загальної купи. Програє той, хто бере останнім, і на столі більше не буде сірників. Для складання логічних рівнянь необхідно сформулювати такі поняття у вигляді предикатів, як можливий хід “can_take_matches( кількість сірників, що можна брати)” і умова виграшу “win( скільки необхідно взяти щоб виграти, загальна кількість сірників)”.
Як можна бачити з програми, розділ domains містить визначення типів даних; розділ “predicates” - опис форми предикатів (які виражають поняття, події, зв'язки, тощо) та типів даних, які в предикатах зустрічаються. Розділ clauses являє собою тіло програми, тому що в ньому визначаються самі логічні умови і зв’язки, які складають логічну модель задачі. Як можна бачити з цього розділу, кожний логічний вираз закінчується крапкою. Можливі два типи виразів:
1. P(X1,X2,...,Xn). - “факти”
2. P(X1,X2,...,Xn):-Q1,Q2,...,Qm. - “правила”
При виконанні предикатів цих типів кожний раз утворюється покоління змінних, яке зникає після того, як програма зустріла крапку кінця предикату. Отже, змінні в предикатах розрізняються лише на протязі виконання даного предикату.
Перший тип предикатів називається фактом. Факт задає жорсткі зв'язки між значеннями своїх змінних. Однойменні факти групуються один біля одного і розглядаються як альтернативи (з умовою “або”): якщо є два факти з одним іменем та різними значеннями змінних, то комбінації значень при уточненні змінних можуть братись повністю з одного, або повністю з другого факту. Наприклад, в поданій нижче програмі факти “can_take_matches” вказують на можливість взяти 1, 2 або 4 сірників.
Вирази другого типу, які містять підстроку “:-” називаються правилами. Позначення “:-” між головою і тілом правила використовується як зв'язка “якщо”, “тоді, коли”, “необхідно” і т.д. Зміст правила виражається в наступному. Для того, щоб предикат P був істинним, необхідно, щоби були істинними всі предикати, які перелічені в правій частині правила. В нашому прикладі - це правило win(X,N), яке визначає умову виграшу. Прочитати це правило можна так: для того, щоб виграти в ситуації з N сірниками, необхідно взяти X сірників, після чого на столі залишиться Z=N-X сірників, яке більше нуля і при даному Z виграш неможливий, що виражено вбудованою функцією not( ). Знак підкреслення в предикаті win(_,Z) означає довільне значення пропущеної змінної, тобто: 1, 2 або 4.
Як не дивно, формулювання понять, які використовуються в алгоритмічних мовах, найбільш важке для декларативних мов програмування. Розглянемо предикат утворення циклу: cycle( змінна циклу, початкове значення, кінцеве значення), який наведений у програмі. Він складається з двох альтернативних правил: присвоїти значення змінній циклу або спробувати перейти до нового значення. Шаблон cycle(N,Y,N) означає, що якщо 1-й параметр не відомий, а 2-й і 3-й відомі, то першому параметру буде присвоєно значення третього параметра, оскільки вони позначені однією змінною N.
Розділ goal вказує кінцеву мету - знайти всі розв’язки задачі від 1 до 12 сірників.
domains
m = integer /* Введено новий тип m - сірники (не число, а тип !) */
/* інші можливі типи: real, string, symbol, char або визначається користувачем */
predicates
can_take_matches(m). /* об'являються назви предикатів і */
win(m,m). /* типи змінних, які в них входять */
cycle(m,m,m). /* can_take_matches - “можна взяти” win - “можна виграти”,
cycle - “цикл” як поняття алгоритмічної мови */
clauses
cycle(N,Begin_value,N):- N>=Begin_value. /* змінна циклу та її границі */
cycle(N,X,Y):- Y>X, N2=Y-1, cycle(N,X,N2). /* умова продовження циклу: якщо кінцеве значення більше початкового, то створюється нова змінна N2 яка активізує нову ітерацію альтернатив - присвоїти конкретне значення змінній циклу чи продовжувати цикл */
can_take_matches(1). /* оголошуються факти, які вірні */
can_take_matches(2). /* при даних значеннях змінних - */
can_take_matches(4). /* задаються альтернативи виконання */
win(X,N):- can_take_matches(X), /* умова виграшу: X - дозволені значення */
Z=N-X, /* N - кількість на даний момент */
Z>0, /* Z - кількість, що залишилась після ходу */
not(win(_,Z)). /* логічне заперечення виграшу протилежної сторони */
/* Знак “_” означає буд-який хід. Предикат вигляду: win...:-...not(win...) задає розв'язок класичної задачі при антагоністичній грі, коли йде боротьба за ресурси по правилах, які однакові для кожної з сторін. Предикат not(win...) задає обмеження на хід, при якому суперник не отримує виграшу, який гарантується при правильній грі. */
goal /* мета програми формулюється як звичайне правило: */
cycle(N,1,12), /* для всіх значень N від 1 до 12 виконати наступне: */
win(X,N),nl, /* знайти розв'язок задачі для N сірників */
write(“ Якщо на столі “,N,” сірників, то для виграшу необхідно взяти “),
write(X,” сірника. “), fail. /* знайти всі можливі рішення */
В цій програмі предикат win(X,N) означає знаходження такого значення X, яке дає гарантований виграш при N сірниках. В процесі розв’язку N=12 лише на початку. В процесі пошуку рішення послідовно будуть виконуватись предикати в правій частині правила win(X,N). Алгоритм знаходження рішення дуже простий. Якщо предикат can_take_matches(X) може бути істинним при деякому X=1, то змінній X присвоюється значення 1 і виконання переходить до наступного предикату. Якщо при даному X=1 можна виконати і наступний предикат, то програма йде далі - робить крок вперед. Якщо на даному кроці рішення не існує, то програма робить крок назад (back tracking) і намагається знайти інше рішення (альтернативу) для попереднього предикату, тобто X=2 для can_take_matches(X). При новому значенні змінних програма робить крок вперед. Якщо всі предикати правила win при деяких значеннях змінних вірні, то задача win(X,12) вирішена при X=2. Пам’ятайте, що всі змінні зберігають свої значення лише на протязі виконання одного правила.
Ключове слово fail завжди хибне і викликає back tracking. Воно дає можливість не зупинятись на знайденому рішенні, а перебрати всі можливі варіанти. В процесі вирішення задачі виконання програми пройде через предикат “win” рівно стільки разів, скільки існує рішень. Предикат “write” вірний завжди і немає альтернативних рішень, тому його можна не враховувати.
Перейдемо до індивідуального завдання. Зрозуміло, що так як елемент “І-НЕ” має один вихід і як мінімум два входи, то відповідний предикат буде оперувати мінімум трьома змінними. Наприклад, можна ввести факт: not_and(1,1,0). Тоді логічну функцію можна записати як правило: my_funct(X,Y,P):-not_and(X,Y,Z),not_and(X,Z,P). Кома завжди означає логічне “І”.
Порядок виконання роботи:
Запустити запропоновану програму, записати таблицю виграшних ходів при заданому N.
Ввести в програму ще одне альтернативне визначення:
win(X,X):-can_take_matches(X). Запустити. Порівняти таблицю виграшних ходів з попередньою. Які зміни відбулися в умові гри при існуванні даного альтернативного визначення?
Закоментувати в програмі весь розділ “goal” та запустити програму в діалоговому режимі. На запит “Goal:” відповісти win(X,11), win(2,12). Записати відповіді.
Скласти свою програму, яка би видавала таблицю істинності для деякої вашої логічної функції. Схема функції має складатися з довільної кількості елементів “І-НЕ”, але не менше ніж з 3-х елементів.
Лабораторна робота 2
Тема: Спискові структури.
Мета роботи: Засвоїти основні поняття для роботи зі списками.
Завдання: Написати та перевірити наступні предикати:
“X є елементом списку Y з номером N”;
“список Z є результатом конкатенації
(з'єднання) списків X та Y”;
“список X є підсписком списку Y”.
Роз'яснення до завдання
Список - це впорядкована множина елементів X1,X2,...XN, з якою можна оперувати як з однією змінною, наприклад: X = [X1,X2,X3,X4].
Для вирішення логічних задач можна складати рівняння над списками. Тоді, крім операції прирівнювання (“=“), яка означає, що всі елементи одного списку повинні співпадати з усіма елементами другого списку, вводиться операція відокремлення елементів списку - “|”. За допомогою операцій прирівнювання та відокремлення можна виразити будь-яке перетворення спискової структури.
Наприклад, рівняння X=[Y|Z] означає, що першим елементом в списку X є елементарний елемент Y, а Z - це всі решта елементів списку. З рівняння [Y1|Z1] = [Y|Z] виходить, що Y1=Y, і Z1=Z. Звичайно, що Y повинно бути одним з простих типів (наприклад: integer, real, char, string, symbol), а Z - списком того самого типу (integer*, real*, char*, string*, symbol*).
Відокремлювати можна декілька елементів, наприклад: X=[Y,P|L]. Якщо до виконання цього предикату прирівнювання деякі з елементів списку, або деякі змінні були невідомі (не зв'язаними), то після виконання прирівнювань невідомі значення стають відомими (зв'язаними), якщо вони прирівнювалися до відомих змінних. Таким чином, вбудований предикат “=“ може бути істинним лише тоді, коли вдалося прирівняти всі підсписки в списковому рівнянні. Відомі змінні можна лише порівнювати, тоді істинність предикату буде залежати від результату порівняння.
Як вже говорилося, в логічній моделі кома між предикатами завжди означає зв'язку “і”, а повторення правил з однаковими головами означає логічне “або” між правими його частинами. В деяких випадках зручно використовувати як “або” символ “;”, але не слід цим зловживати, тому що програма не є наглядною, наприклад:
I_want_buy(Car_model,Price,Color):- not(Color=“blue”);not(Color=“white”)
є тавтологією, тому що колір завжди або не синій, або не білий.
Нижче подана проста демонстраційна програма для визначення невідомого чотирьохзначного числа. В ній до Вашого розгляду запропоновано один стандартний прийом вирішення логічних задач. Він полягає у висуванні пропозиції і перевірці, чи підійде вона для розв'язку задачі (дивіться предикат response у програмі). Для цієї перевірки використовується стандартна функція not, вживання якої засновано на класичному зв'язку кванторів “існує” та “всі”. Отже, “не існує об'єкту X” означає що “всі об'єкти не X”.
В даній програмі взаємоперетворення кванторів здійснено у предикаті not(bad_check(Code)), що означає “не існує bad_check”. Завдяки тому відбувається неявний перебір всіх можливих рішень bad_check, які базуються на базі даних “history”.
Domains /* задаємо тип “список цілих чисел” */
cod=integer*
Predicates /* визначаємо типи предикатів */
propose(cod)
choice(integer,cod)
response(cod)
bad_check(cod)
check1(cod,cod,integer)
read(integer)
go(integer)
Database
/* визначаємо базу даних запитів та відповідей, яка поповнюється в процесі вирішення задачі */
history(cod, integer)
Clauses /* логічна модель задачі: */
/* вибір числа X зі списку */
choice(X,[X|_]). /* означає, що за X можна прийняти перший елемент, підкреслення означає будь-яке значення */
choice(X,[_|L]):-choice(X,L). /* або X вибрати з решти елементів L. */
/* Пропозиція загаданого коду - це список з чотирьох довільних цифр */
propose(Code):-choice(X1,[0,1,2,3,4,5,6,7,8,9]),
choice(X2,[0,1,2,3,4,5,6,7,8,9]),
choice(X3,[0,1,2,3,4,5,6,7,8,9]),
choice(X4,[0,1,2,3,4,5,6,7,8,9]),
Code=[X1,X2,X3,X4]. /* Code - це загальний вигляд списку з 4-х елементів. */
/* response - це пошук такого списку “Code”, який не суперечить всім попереднім запитам і відповідям. */
response(Code):-propose(Code), /* це пропозиція, яка */
not(bad_check(Code)). /* не суперечить іншим відповідям БД */
/* bad_check=true, якщо пропозиція “Code” суперечить одному з записів БД */
bad_check(Code):- history(Code2,X1), /* у базі даних */
check1(Code,Code2,X), /* існує така відповідь, */
X<>X1. /* яка суперечить даній пропозиції “Code”. */
/* В предикаті check1 знаходиться число X, яке означає кількість цифр, які стоять на своїх місцях, якщо Code - це задумане число, а Code2 - це пропозиція. Відповідь X1, яка була дана раніше на пропозицію Code2 повинна співпадати з X, яке вираховує предикат порівняння кодів check1. */
/* алгоритм порівняння пропозиції з задуманим кодом і визначення кількості цифр, що співпадають */
check1([],[],0). /* порожні коди не мають співпадінь */
check1([X|Lx],[X|Ly],N1):-check1(Lx,Ly,N3),N1=N3+1. /* якщо в двох кодах співпадають перші елементи, то вирішити задачу для решти елементів і до результату N3, який буде отриманий, додати одиницю. */
check1([X|Lx],[Y|Ly],N1):-X<>Y,check1(Lx,Ly,N1). /* якщо перші елементи не співпадають, то перейти до порівняння решти елементів. */
/* read - це предикат для введення числа від 1 до 4: */
read(X):-readint(X),X>=0,X<5,!. /* знак “!” означає, що інших розв'язків для даного предикатного рівняння шукати не потрібно, якщо число введено правильно */
read(X):-write(“Будьте уважні! “),read(X). /* альтернатива при невірному вводі */
/* процес діалогу (запит, відповідь та збереження у БД запиту та відповіді) */
go(N):-N>0, /* N - кількість спроб, які даються для вирішення */
response(Code),write(“я вважаю, ви задумали число “),
write(Code),nl,
write(“Введіть кількість цифр, які стоять на своїх місцях:”),
read(X),assert(history(Code,X)),
/* assert - стандартний предикат запису в кінець БД. */
X<4,nl, /* якщо число не вгадане, X<4, */
N1=N-1,go(N1). /* перейти до наступного ходу go(N1) */
go(N):- N>0,response(_), /* існує така відповідь, яка не суперечить БД */
write(“ Я вгадав. Залишилось “,N,” спроб.”).
go(0):-nl,write(“ Я ПРОГРАВ!”). /* якщо спроб не залишилось, то N=0 */
go(N):-N>0,not(response(_)), /* не існує відповіді, яка не суперечить БД */
nl,write(“ Ви невірно відповіли!”),nl.
Goal /* Опис загальної послідовності виконання предикатів */
retractall(history(_,_)), /* для порожньої бази даних виконати:
retractall - стандартний предикат, який знищує БД */
write(“ Я вгадаю ваше чотирьохзначне число за 15 спроб.”),
nl,write(“Запишіть його на папері. Записали ?”),readln(_),
nl,go(15).
Порядок виконання роботи:
Запустити програму. Записати відповіді програми та ваші відповіді.
Знайти число, яке програма вгадує за найбільшу кількість спроб.
В діалоговому режимі запустити окремі предикати, які викликали запитання.
Скласти предикати, які запропоновані в завданні.
Скласти звіт та висновки по роботі.
Лабораторна робота 3
Тема: Інтерпретація PROLOG-програм.
Мета: зрозуміти механізм виконання PROLOG-програм.
Завдання: Скласти алгоритм, який виникає в результаті інтерпретації логічної моделі сортування, яка описана нижчеподаною програмою.
Роз'яснення до завдання.
Процес отримання результату роботи PROLOG-програм зв'язаний з виконанням деякого алгоритму на комп'ютері. Оскільки PROLOG - не алгоритмічна, а декларативна мова програмування, то алгоритм її виконання залежить від алгоритму інтерпретації предикатів, з яких складається програма. В лабораторній роботі запропоновано закріпити лекційний матеріал і розглянути алгоритм інтерпретації предикату “sort” по кроках.
Domains
l=integer* /* l-список цілих чисел */
Predicates
sort(l,l) /* предикат сортування */
partition(l,integer,l,l) /* розбиття списку на два підсписки */
append(l,l,l) /* предикат з'єднання двох списків */
Clauses
partition([],_,[],[]). /* Розбиття списку на два підсписки -
тривіальний випадок, коли початковий
список порожній */
partition([X|Lx],Y,[X|B1],B2):- X<=Y,partition(Lx,Y,B1,B2).
/* Коли перший елемент меньше заданого Y,
приєднуємо його до першого підсписку; */
partition([X|Lx],Y,B1,[X|B2]):- X>Y,partition(Lx,Y,B1,B2).
/* Коли перший елемент більше заданого Y,
приєднуємо його до другого підсписку; */
sort([],[]). /* випадок тривіального сортування */
sort([X|Lx],Y):-partition(Lx,X,Litles,Bigs),
/* розбиваємо список на елементи, які меньше
першого, і елементи, які більше першого */
sort(Litles,Left),sort(Bigs,Right),
/* рекурсивно сортуємо кожний підсписок */
append(Left,[X|Right],Y).
/* та з'єднуємо їх з першим елементом. */
append([],Y,Y). /* тривіальне з'єднання списків */
append([X|Lx],Y,[X|Ls]):-append(Lx,Y,Ls). /* рекурсивне правило
з'єднання двох списків: рішення складної задачі
виражено через рішення такої самої простої задачі.*/
Порядок виконання роботи
1. Запустити програму На запит “goal:” задати sort([список чисел],X).
2. Задати append(X,Y,[список чисел]).
3. Задати partition([3,-5,12,7,1],6,X,Y).
4. Записати протокол трасування предикату sort([3,-5,12,7,1],X).
Лабораторна робота 4
Тема: Стрічкові змінні та предикати над стрічками.
Мета: дати основу для обробки текстової інформації.
Завдання: Написати програму для перетворення стрічки в список символів.
Роз'яснення до завдання
Поняття стрічки для багатьох мов програмування є фундаментальним. Стрічка - це скінчена послідовність символів, яка має свою назву, і з якою можна працювати як зі змінною. Від списку стрічка відрізняється лише тим, що елементами списку можуть бути довільні об'єкти, а стрічка може містити лише символи. Абстрактне поняття стрічки дозволяє розглядати довільний файл як стрічку. Така уніфікація дозволяє застосовувати стрічкові операції до файлів. Приклад відкриття файлу, читання даних з нього, а також запис у файл наведено нижче. В цій програмі використано декілька стандартних предикатів, зміст яких вам необхідно вияснити. В довіднику, який додається до методичних вказівок, крім означених предикатів є наступні: frontchar(X,Y,Z), frontstr(N,X,Y,Z), strlen(X,N), isname(X), str_int(X,N), str_real(X,R), upper_lower(X,Y), зміст яких також необхідно вияснити в процесі лабораторної роботи. Як звичайно, кожний з параметрів у перелічених вище предикатах може бути як вхідним, так і вихідним.
Predicates
a /* запис слова у файл “text.txt” */
b(string) /* роздрук всіх слів в стрічці */
Clauses
a:- file_str(“text.txt”,X),
/* Розглядати файл “text.txt” як стрічку символів */
b(X), /* роздрукувати її по окремих словах */
write(“input the word please:”),
readln(Y), /* ввести нове слово */
concat(X,Y,Z), /* з'єднати: Z = X¦Y */
file_str(“text.txt”,Z). /* записати у файл “text.txt” */
b(X):- fronttoken(X,Y,Z), /* від'єднати від X слово Y */
write(Y),nl,b(Z). /* роздрукувати його та повторити */
b(_). /* передбачено на випадок, коли стрічка закінчиться,
предикат b повинен повернути значення “true”. */
Порядок виконання роботи.
1. Створити у робочому каталозі PROLOG'а файл “text.txt”.
2. Розібратись, як працює запропонована програма.
3. Розібратись, як працюють вбудовані стрічкові предикати.
4. Використовуючи предикат “frontchar” та операцію відокремлення першого елементу X від решти елементів Y списку [X|Y], написати свою програму, яка була запропонована в завданні до роботи.
Скласти звіт по роботі.
Лабораторна робота 5
Тема: Графові моделі
Мета: дати основу для розв’язку задач на графах.
Завдання: ознайомитись з методом вирішення логічних задач за допомогою
бази даних перетворень станів системи.
Роз'яснення до завдання
Графи можна представляти як у вигляді списків, так і у вигляді множини фактів типу “ребро, що з’єднує вершини А і Б довжини L”. Останній метод є найбільш поширений і простий. Для пошуку всіх вершин, які були знайдені в результаті задачі на графі існує вбудований предикат findall(X,P(X),Z), де X - змінна, P(X) - предикат, в якому є змінна X, а Z - список зі значень змінної X, який буде сформований в результаті вирішення задачі.
Розглянемо приклад вирішення простої задачі на графі. Нехай задано три відра bottle(номер відра, об'єм відра) відповідно по 12, 8 і 5 літрів. Початковий стан даної “системи” [12,0,0]. Необхідно перевести систему в стан [6,6,0] за мінімальну кількість кроків. Кроком вважається переливання рідини з одного відра в друге. Це можна зробити одним з двох варіантів: 1) вилити рідину повністю з одного відра в інше 2) долити в відро рідину до верху з іншого відра за допомогою правила: mov_water(номер відра з якого виливають, номер відра куди вливають, стан до операції, стан після операції ).
Правила функціонування даної “системи” задають граф переходів між її станами, який фіксується в базі даних states(стан системи до операції, стан системи після операції). Стан системи, як вже було згадано, задається у вигляді списку з трьох елементів, де кожний елемент відповідає кількості рідини в кожному відрі.
Такі задачі вирішуються в два етапи. На першому - заповнюється база даних можливих станів системи - find_states(початковий стан системи). Фактично, це знаходження всіх станів системи з заданого початкового стану. Якщо в базі даних деякого стану немає, то досягнути його неможливо. На другому етапі розв'язку задачі знаходиться вивід необхідного стану системи з бази даних за допомогою предикату way(кінцевий стан системи).
Domains
n=integer /* номер відра */
b=integer /* об'єм відра */
l=integer* /* список відер */
Predicates
bottle(n,b) /* таблиця номер відра - об'єм */
mov_water(n,n,l,l) /* якщо перелити, що буде ? */
member(l,n,b) /* елемент списку */
replace(l,l,n,b) /* замінити елемент в списку */
find_states(l) /* знайти всі стани системи */
print_basa /* роздрукувати всі стани */
way(l) /* знайти шлях в базі даних */
Database
states(l,l) /* база даних “попередній стан - наступний стан” */
Clauses
bottle(1,12). /* перше відро на 12 літрів */
bottle(2,8). /* друге відро на 8 літрів */
bottle(3,5). /* трете відро на 5 літрів */
/* класичне визначення елементу списку [X|Y] */
member([X|_],1,X).
member([_|L],N,X):- member(L,N1,X), N=N1+1.
/* заміна в першому списку елементу з номером N на елемент K */
replace([_|L],[K|L],1,K).
replace([X|L1],[X|L2],N,K):- replace(L1,L2,N1,K), N=N1+1.
mov_water(N1,N2,L1,L2):- bottle(N1,_), /* правило виливання води до кінця відра */
member(L1,N1,P), P>0,
bottle(N2,K), N1<>N2,
member(L1,N2,Q),
Z=P+Q, Z<=K,
replace(L1,L,N1,0),
replace(L,L2,N2,Z).
mov_water(N1,N2,L1,L2):- bottle(N1,_), /* правило доливання води в відро до верху */
member(L1,N1,P), P>0,
bottle(N2,K), N1<>N2,
member(L1,N2,Q), Q<K,
Z=P-K+Q, Z>0,
replace(L1,L,N1,Z),
replace(L,L2,N2,K).
/* процес розливання води - це ввід в базу данних за допомогою вбудованого предикату assertz(факт бази даних) всіх станів, які можна досягнути з початкового. */
find_states(L1):- mov_water(N1,N2,L1,L),
not(states(_,L)),assertz(states(L1,L)),fail.
find_states(_):- states(_,L1), /* ввід в базу даних станів, */
mov_water(N1,N2,L1,L), /* які можна досягнути з станів бази даних. */
not(states(_,L)),assertz(states(L1,L)),fail. /* Повторення станів заблоковано */
find_states(_). /* виконується, коли пошук закінчено */
/* знаходження виводу комбінації L1 */
way(L1):-states(L,L1),retract(states(L,L1)),write(L1,” “),way(L).
/* роздрук бази даних різних комбінацій розливу */
print_basa:- states(L1,L2),write(L1,” “,L2),nl,fail.
print_basa.
Goal
retractall(states(_,_)), find_states([12,0,0]), print_basa, nl, way([6,6,0]).
Порядок виконання роботи:
1. Запустити запропоновану програму.
2. Вивести стани системи у
14.02.2013 15:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора