Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Спискові структури
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук і технологій
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2006
Тип роботи:
Лабораторна робота
Предмет:
Логічне програмування
Група:
ІУС-51
Частина тексту файла (без зображень, графіків і формул):
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук і технологій
Кафедра АСУ
Лабораторна робота №2
з курсу „Логічне програмування”
Тема: «Спискові структури»
Виконав:
студент групи ІУС-51
Перевірив:
Львів-2006
Мета роботи: Засвоїти основні поняття для роботи зі списками.
Теоретичні відомості
Список – це впорядкована множина елементів 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).
Хід роботи
Завдання: вгадати назву міста з 5 літер.
domains
cod=char*
predicates
propose(cod).
choice(char,cod).
response(cod).
bad_check(cod).
check1(cod,cod,char).
read(integer).
go(integer).
Database
history(cod, integer).
clauses
choice(X,[X|_]).
choice(X,[_|L]):-choice(X,L).
propose(Name):-choice(X1,['a','m','d','l','k','n','q','r','z']),
choice(X2,['a','q','r','s','t','v','w','x','z']),
choice(X3,['a','y','i','o','u','b','c','d','f']),
choice(X4,['a','e','y','k','o','f','g','h','j']),
choice(X5,['a','e','l','i','o','u','b','c','d']),
Name=[X1,X2,X3,X4,X5].
response(Name):-propose(Name),not(bad_check(Name)).
bad_check(Name):- history(Name2,X1),check1(Name,Name2,X),X<>X1.
check1([],[],0).
check1([X|Lx],[X|Ly],N1):-check1(Lx,Ly,N3),N1=N3+1.
check1([X|Lx],[Y|Ly],N1):-X<>Y,check1(Lx,Ly,N1).
read(X):-readint(X),X>=0,X<6,!.
read(X):-write("Bydte yvazni! "),read(X).
go(N):-N>0,response(Name),write("Napevno zadymalu "),nl,write(Name),nl,
write("Vvedit kilkist liter, wo stojat na svoix miscjax:"),read(X),assert(history(Name,X)),
X<5,nl,N1=N-1,go(N1).
go(N):- N>0,response(_),nl,write(" !!!JA VGADALA!!!"),nl,write(" Zaluwulos ",N," sprob.").
go(0):-nl,write(" JA PROGRALA!").
go(N):-N>0,not(response(_)),nl,write(" Vu nevirno vidpovilu!"),nl.
goal
retractall(history(_,_)),
write(" Ja vgadajy kluchky sobaku z 5 liter za"),nl,write(" 20 sprob."),nl,
nl,write("Zapuwit ii na paperi. Zapusalu?"),readln(_),
nl,go(20).
Висновок: в даній лабораторній роботі я засвоїв основні поняття для роботи зі списками, вивчив, основні логічні операції, які можна виконувати над списками і як для прикладу створив логічну програмульку для вгадування назви міст що має 5 літер.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора