лп / Krtuvorychko / otchet_7
.docМіністерство освіти і науки, молоді і спорту України
Кіровоградський національний технічний університет
Механіко-технологічний факультет
Кафедра програмного забезпечення
Дисципліна: « Логічне програмування »
Лабораторна робота № 7
Тема: «Робота з графами на мові програмування Turbo Prolog»
Виконав: ст. групи КІ-12-СК
Криворучко О.В.
Перевірив: викладач
Резніченко В.А.
Кіровоград 2013
Мета: Розглянути основні операції над графами на мові програмування Turbo Prolog.
Завдання:
-
Зобразити на папері індивідуальний маршрут довільної поїздки.
-
Скласти програму, яка виводить на екран всі можливі варіанти шляху між вказаними пунктами з переліком проміжних пунктів і їх кількості. Передбачається, що рухатись можна в прямому і в зворотньому напрямках. Рекомендується використовувати списки.
Граф:
Лістинг програми:
domains
s=symbol
sp=symbol*
i=integer
predicates
p(s,s)
road(s,s,sp)
puti(s,s)
kol(sp,i)
clauses
p(kirowohrad,odessa).
p(odessa,illichevsk).
p(odessa,ismail).
p(odessa,krivojroh).
p(ismail,krivojroh).
p(kirowohrad,dnepropetrovsk).
p(dnepropetrovsk,krivojroh).
p(dnepropetrovsk,dneprodzerjunsk).
p(dneprodzerjunsk,gorlovka).
p(kirowohrad,donetsk).
p(donetsk,gorlovka).
p(donetsk,makeevka).
p(dnepropetrovsk,gorlovka).
road(X,X,[X]).
road(X,Y,[X|P]):-p(X,N),road(N,Y,P).
puti(X,Y):-road(X,Y,Z1),
road(X,Y,Z2),
kol(Z1,N1),kol(Z2,N2),N1<N2,nl,
write(N1," Puti"),nl.
kol([],0).
kol([G|H],N):-write(G),kol(H,P),N=P+1.
Рис.1 – виконання програми
Контрольні питання:
-
Що таке орієнтований граф?
Граф визначається як множина вершин разом з множиною ребер, причому кожне ребро задається парою вершин.
-
Які способи представлення графів в Turbo Prolog ви знаєте?
В Turbo Prolog графи можна представляти різними способами. Один з них – кожне ребро записувати у вигляді одного речення.
Другий спосіб – весь граф представляти як один об’єкт. В цьому випадку графу відповідає пару множин = множина вершин і множина ребер. Кожну множину можна задавати за допомогою списку, кожне ребро – парою вершин.
Ще один спосіб представлення графа – зв’язати з кожною вершиною список суміжних з нею вершин. В цьому випадку граф перетворюється в список пар, кожна з яких складається з вершини та її списку суміжності.