Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Эйлеров цикл
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
igorit igorit вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.04.2010
По умолчанию 15.04.2010, 04:32

Я переписал прогу с вашего форума

Код:
domains
sl=symbol*
predicates
nondeterm a(symbol,symbol)
nondeterm b(symbol,symbol)
nondeterm цикл(symbol,sl,sl,integer,integer)
принадл(symbol,symbol,sl)
длиннее(symbol,integer)

clauses
a(a,b). a(b,c). a(d,c). a(d,f). a(f,c). a(a,c).

b(X,Y):- a(X,Y); a(Y,X).

цикл(X,V,L,D,Di):- b(X,Y),not(принадл(X,Y,V)),D1=D+1,
    цикл(Y,[Y|V],L,D1,Di).
цикл(_,L,L,Di,Di).

принадл(X,Y,[X,Y|_]):- !.
принадл(X,Y,[Y,X|_]):- !.
принадл(X,Y,[_|T]):- принадл(X,Y,T).

длиннее(X,D):- цикл(X,[X],_,0,D1),D<D1,!.
goal
X=a,цикл(X,[X],Цикл,0,D),not(длиннее(X,D)).

Результат
Код
X=a, Цикл=["a","c","f","d","c","b","a"], D=6
X=a, Цикл=["a","c","d","f","c","b","a"], D=6
X=a, Цикл=["a","b","c","f","d","c","a"], D=6
X=a, Цикл=["a","b","c","d","f","c","a"], D=6
4 Solutions

Получилось

a(a,b). 
a(b,c). 
a(d,c). 
a(d,f). 
a(f,c). 
a(a,c).

b(X,Y):- a(X,Y);a(Y,X).
цикл(X,V,L,D,Di):- b(X,Y),not(принадл(X,Y,V)),D1 is D+1,
    цикл(Y,[Y|V],L,D1,Di).
цикл(_,L,L,Di,Di).

принадл(X,Y,[X,Y|_]):- !.
принадл(X,Y,[Y,X|_]):- !.
принадл(X,Y,[_|T]):- принадл(X,Y,T).

длиннее(X,D):- цикл(X,[X],_,0,D1),D<D1,!.
Она компилится, но выдаёт только одно решение. Как это исправить и как реализовать проверку графа на наличие эйлерового цикла?
Ответить с цитированием
  (#2 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 15.04.2010, 18:58

Чтобы получить следующее решение, нажмите ; (точку с запятой).
Так она и проверяет на наличие эйлерова цикла (можно и по-другому, конечно).
Ответить с цитированием
  (#3 (permalink)) Старый
igorit igorit вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.04.2010
По умолчанию 17.04.2010, 12:29

Имея виду проверку на эйлеров цикл я хотел показать, что если задать другой граф
Пример
Код:
a(a,b). 
a(b,c).
a(c,d). 
a(d,b). 
a(d,a). 

b(X,Y):- a(X,Y).
b(X,Y):- a(Y,X).
цикл(X,V,L,D,Di):- b(X,Y),not(принадл(X,Y,V)),D1 is D+1,
    цикл(Y,[Y|V],L,D1,Di).
цикл(_,L,L,Di,Di).

принадл(X,Y,[X,Y|_]):- !.
принадл(X,Y,[Y,X|_]):- !.
принадл(X,Y,[_|T]):- принадл(X,Y,T).

длиннее(X,D):- цикл(X,[X],_,0,D1),D<D1,!.
, то прога не выдаст ложь, хотя граф не эйлеров.
Ответить с цитированием
  (#4 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 17.04.2010, 22:27

Вот так можно сделать:
Код:
domains
sl=symbol*
edge=e(symbol,symbol)
el=edge*
database
a(symbol,symbol)
predicates
nondeterm b(symbol,symbol)
nondeterm цикл(symbol,el,el,integer)
принадл(edge,el)
эйлеров(el)
количествоРебер(integer)
длина(sl,integer)
clauses
a(a,b). a(b,c). a(d,c). a(d,f). a(f,c). a(a,c). 

b(X,Y):- a(X,Y); a(Y,X).

эйлеров(Цикл):-
    количествоРебер(D),
    b(X,Y),
    цикл(X,[e(Y,X)],Цикл,D),
    !.

количествоРебер(D):-
    findall(X,a(X,_),L),
    длина(L,D).

длина([],0).
длина([_|L],N):- длина(L,N1), N=N1+1.

цикл(X,[e(X,Y)|L],[e(X,Y)|L],1):- !.
цикл(Start,[e(Y,X)|V],L,D):- D>0, 
    b(Y,Z),Z<>X,
    not(принадл(e(Z,Y),V)),
    D1=D-1,
    цикл(Start,[e(Z,Y),e(Y,X)|V],L,D1).

принадл(E,[E|_]):- !.
принадл(e(X,Y),[e(Y,X)|_]):- !.
принадл(E,[_|T]):- принадл(E,T).
goal
эйлеров(Цикл).
Выдаст либо первый найденный эйлеров цикл, либо ложь если граф не эйлеров.
Вообще можно сделать еще большим количеством способов.
Ответить с цитированием
  (#5 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,374
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 18.04.2010, 01:45

Рёбра пересчитывать не обязательно. Равно как и стартовать из всех вершин по очереди - "цикл" и всё тут, а не "путь":
Код:
DOMAINS
s=symbol   sl=s*
CONSTANTS
graf1=[a,b,  b,c,  d,c,  d,f,  f,c,  a,c] 
graf2=[a,b,  b,c,  c,d,  d,b,  d,a]
PREDICATES
rp(s,s,sl,sl)
cycle(s,s,sl,sl)
ifEyler(sl,sl)
CLAUSES
ifEyler(Graf,Way):- Graf=[Start|_], cycle(Start,Start,Graf,Way), !.

cycle(A,A,[],[A]):- !.
cycle(A,F,Gr,[A|B]):- rp(A,C,Gr,GrN), cycle(C,F,GrN,B).

rp(A,B,[A,B|C],C).
rp(A,B,[B,A|C],C).
rp(A,B,[C,X|D],[C,X|F]):- rp(A,B,D,F).
Код:
Goal: ifEyler(graf1,Way)
Way=["a","b","c","d","f","c","a"]
1 Solution
Goal: ifEyler(graf2,Way)
No Solution
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,374
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 19.04.2010, 16:31

Код:
implement main
    open core, console, list
constants
    className = "main".
    classVersion = "".

class facts
     gr1 : char* :=['a','b',     'b','c',     'd','c',     'd','f',      'f','c',     'a','c']. 
     gr2 : char* :=['a','b',     'b','c',     'c','d',     'd','b',     'd','a'].
     gr3 : char* :=['a','b',     'b','c',     'b','d'].
class predicates    
     eyler : (char*,string) -> char* procedure(i,o).
     way : (char,char,char*) -> char* nondeterm (i,i,i) (i,o,i).
     rp : (char,char*,char*) -> char nondeterm (i,i,o).
clauses
  classInfo(className, classVersion).
    
      eyler(Graf, "cycle") = B:- Graf=[A|_], B=way(A,A,Graf), !.
      eyler(Graf, "way") = B:- B=way(getMember_nd(removeDuplicates(Graf)),_,Graf), !.
      eyler(_, "no cycle, no way") = [].
    
    way(A,A,[]) = [A]:- !.
    way(A,F,Gr) = [A|way(rp(A,Gr,GrN),F,GrN)].

    rp(A,[A,B|C],C) = B.
    rp(A,[B,A|C],C) = B.
    rp(A,[B,C|D],[B,C|E]) = rp(A,D,E).
    
run():- init(), W=eyler(gr3,Mes), write(Mes), nl, if W<>[] then write("example: ",W) end if, _=readchar().

end implement main
goal
   main::run.
Ответить с цитированием
  (#7 (permalink)) Старый
misha11 misha11 вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 22.10.2014
По умолчанию 22.10.2014, 21:15

Как запустить эту программу?
Ответить с цитированием
  (#8 (permalink)) Старый
goal goal вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 2
Поблагодарили 3 раз(а) в 3 сообщениях
Регистрация: 16.10.2014
По умолчанию 22.10.2014, 21:36

Запускаете VIP 7.5. New Project. Вводите имя проекта и нажать кнопку Finish. С минуту ждете до 100% компиляции. Открываете файл main.pro. Ctrl+S, Ctrl-X, Ctrl-C, Ctrl-V. И затем кнопочка "E".
Ответить с цитированием
  (#9 (permalink)) Старый
misha11 misha11 вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 22.10.2014
По умолчанию 22.10.2014, 22:49

Я имел виду
domains
sl=symbol*
edge=e(symbol,symbol)
el=edge*
database
a(symbol,symbol)
predicates
nondeterm b(symbol,symbol)
nondeterm цикл(symbol,el,el,integer)
принадл(edge,el)
эйлеров(el)
количествоРебер(integer)
длина(sl,integer)
clauses
a(a,b). a(b,c). a(d,c). a(d,f). a(f,c). a(a,c).

b(X,Y):- a(X,Y); a(Y,X).

эйлеров(Цикл):-
количествоРебер(D),
b(X,Y),
цикл(X,[e(Y,X)],Цикл,D),
!.

количествоРебер(D):-
findall(X,a(X,_),L),
длина(L,D).

длина([],0).
длина([_|L],N):- длина(L,N1), N=N1+1.

цикл(X,[e(X,Y)|L],[e(X,Y)|L],1):- !.
цикл(Start,[e(Y,X)|V],L,D):- D>0,
b(Y,Z),Z<>X,
not(принадл(e(Z,Y),V)),
D1=D-1,
цикл(Start,[e(Z,Y),e(Y,X)|V],L,D1).

принадл(E,[E|_]):- !.
принадл(e(X,Y),[e(Y,X)|_]):- !.
принадл(E,[_|T]):- принадл(E,T).
goal
эйлеров(Цикл).

Когда запускаю, не выводит Эйлеров цикл
Ответить с цитированием
  (#10 (permalink)) Старый
compasses compasses вне форума
Member
 
Сообщений: 44
Сказал(а) спасибо: 1
Поблагодарили 8 раз(а) в 8 сообщениях
Регистрация: 25.02.2014
По умолчанию 22.10.2014, 23:20

misha11, а что выводит? как запускаешь? чем больше информации расскажешь, тем вернее тебе помогут.
Ответить с цитированием
  (#11 (permalink)) Старый
Винитарх Винитарх на форуме
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,884
Сказал(а) спасибо: 2
Поблагодарили 293 раз(а) в 293 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 22.10.2014, 23:23

Запускать в любом Прологе от Турбы до VIP5.2
В VIP (до ver 5.2) надо указать внутреннюю цель:
goal ifEyler(graf1,Way).
В Турбе эту цель можно указать как внутреннюю, так и внешнюю.
Ответить с цитированием
  (#12 (permalink)) Старый
misha11 misha11 вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 22.10.2014
По умолчанию 23.10.2014, 09:57

Цитата:
Сообщение от Винитарх Посмотреть сообщение
Запускать в любом Прологе от Турбы до VIP5.2
В VIP (до ver 5.2) надо указать внутреннюю цель:
goal ifEyler(graf1,Way).
В Турбе эту цель можно указать как внутреннюю, так и внешнюю.
Не могли бы объяснить алгоритм работы? Зачем используется длина ([],0).
длина ([_|L],N):- длина(L,N1), N=N1+1.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 23.10.2014, 10:18

В VIP 5.2 все выводится. В Турбо Прологе, наверное, нужно использовать write для внутренней цели.

Предикат длина находит длину списка. Эйлеров цикл по определению содержит все ребра графа по одному разу, вот они и отсчитываются.
Ответить с цитированием
  (#14 (permalink)) Старый
misha11 misha11 вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 22.10.2014
По умолчанию 23.10.2014, 19:38

Не могли бы объяснить все программу, как работает.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
как придумать цикл михаил273 С/С++ 3 20.03.2012 23:02
цикл михаил273 Visual C++ 0 19.03.2012 20:13
Гамильнонов цикл Лизочка Prolog 1 01.12.2011 14:35
Цикл с ветвлениями Jalced Pascal 1 12.10.2011 11:30
Эйлеров цикл... 4ixOn Prolog 1 02.06.2011 11:04
Цикл while! Даниэла Pascal 1 19.01.2011 21:58
Эйлеров цикл для Java Internet Prolog constellation Prolog 0 30.11.2008 18:47
Эйлеров путь Dimitsuri Prolog 1 03.09.2007 17:08
Гамильтонов цикл AlexBugor Prolog 3 23.11.2006 18:14
написать решение задачи про эйлеров цикл Ninel Prolog 1 20.01.2006 21:20
Как сформировать цикл Romashka Pascal 5 16.10.2005 08:14
цикл в цикле imported_Tweety Prolog 1 17.01.2005 01:46



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов