Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Интересная задача о КОНВЕРТЕ
Ответ
 
Опции темы Опции просмотра
  (#16 (permalink)) Старый
Stom Stom вне форума
Новичок
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2007
По умолчанию 30.11.2007, 15:14

Получилось! вот код:

Код:
domains
текущая = integer
ребро = ребро(string,integer,integer)
пройденые = string*

predicates
nondeterm является_элементом(string,пройденые)
длина(пройденые, integer)
nondeterm writel(пройденые)
nondeterm найти_путь(integer,пройденые)
nondeterm ребро(string,integer,integer)
clauses
ребро("а",1,2).
ребро("а",2,1).

ребро("б",2,3).
ребро("б",3,2).

ребро("в",1,3).
ребро("в",3,1).

ребро("г",2,4).
ребро("г",4,2).

ребро("д",2,5).
ребро("д",5,2).

ребро("е",4,3).
ребро("е",3,4).

ребро("ж",3,5).
ребро("ж",5,3).

ребро("з",4,5).
ребро("з",5,4).

длина([],0).
длина([_|А],Л):- длина(А,Длинахвоста), Л=Длинахвоста+1.

является_элементом(Ребро,[Ребро|_]).
является_элементом(Ребро,[_|Пройденые]):- является_элементом(Ребро,Пройденые).

writel([]).
    writel([Ребро|A]):-
        writel(A),
        %write("\n"),
        write(Ребро),write(" ").

найти_путь(_,Пройденые):-длина(Пройденые,8),writel(Пройденые).

найти_путь(Текущая,Пройденые):-ребро(Ребро,Текущая,Новая),Not(является_элементом(Ребро,Пройденые)),найти_путь(Новая,[Ребро|Пройденые]).    

goal
найти_путь(4,[]).
Теперь еще небольшое усложнение - нужно, чтобы ребро "г" обходилось 2 раза
Ответить с цитированием
  (#17 (permalink)) Старый
Stom Stom вне форума
Новичок
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2007
По умолчанию 02.12.2007, 22:45

Ответить с цитированием
  (#18 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 03.12.2007, 00:11

г - два раза проходить не надо. Эйлеров путь - это путь, который проходит через все ребра графа по одному разу.
В данном случае он может начинаться и заканчиваться только в вершинах 4 и 5, они имеют нечетную степень.
Код:
domains
текущая = integer
ребро = ребро(string,integer,integer)
sl = string*

predicates
nondeterm является_элементом(string,sl)
реверс(sl,sl,sl)
determ write1(integer,sl)
nondeterm найти_путь(integer,sl,sl,integer)
nondeterm дуга(string,integer,integer)
nondeterm ребро(string,integer,integer)
nondeterm эйлеров_путь(integer,sl)

clauses
дуга("а",1,2).
дуга("б",2,3).
дуга("в",1,3).
дуга("г",2,4).
дуга("д",2,5).
дуга("е",4,3).
дуга("ж",3,5).
дуга("з",4,5).

ребро(Ребро,Начало,Конец):-
    дуга(Ребро,Начало,Конец);
    дуга(Ребро,Конец,Начало).

реверс([А|П],С,Р):- реверс(П,[А|С],Р).
реверс([],П,П).

является_элементом(Ребро,[Ребро|_]).
является_элементом(Ребро,[_|Пройденые]):- 
    является_элементом(Ребро,Пройденые).

write1(В,[]):- write(В).
write1(В,[Ребро|A]):-
    ребро(Ребро,В,В1),
    !,
    writef("% - % - ",В,Ребро),
    write1(В1,A).

найти_путь(_,Путь,Путь,0):- !.
найти_путь(Текущая,Пройденые,Путь,Д):-
    ребро(Ребро,Текущая,Новая),
    not(является_элементом(Ребро,Пройденые)),
    Д1 = Д - 1,
    найти_путь(Новая,[Ребро|Пройденые],Путь,Д1).
    
эйлеров_путь(Вершина,Путь):-
    найти_путь(Вершина,[],Путь1,8),
    реверс(Путь1,[],Путь),
    nl,
    write1(Вершина,Путь).

goal
эйлеров_путь(4,Путь),nl.
Всего из вершины 4 в вершину 5 находятся 44 эйлеровых пути. Вот первый из них:
Код:
4 - е - 3 - ж - 5 - д - 2 - б - 3 - в - 1 - а - 2 - г - 4 - з - 5
Путь=["е","ж","д","б","в","а","г","з"]
Ответить с цитированием
  (#19 (permalink)) Старый
Stom Stom вне форума
Новичок
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2007
Unhappy 03.12.2007, 00:36

Цитата:
г - два раза проходить не надо. Эйлеров путь - это путь, который проходит через все ребра графа по одному разу.
В данном случае он может начинаться и заканчиваться только в вершинах 4 и 5, они имеют нечетную степень.
Все верно, моя предыдущая работает аналогично - с этим вопросов нет. Мне усложнили задачу и нужно, чтобы ребро "г" обходилось 2 раза
Ответить с цитированием
  (#20 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 03.12.2007, 12:38

А что нужно найти в таком случае?
Ответить с цитированием
Ads.
  (#21 (permalink)) Старый
Stom Stom вне форума
Новичок
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2007
По умолчанию 03.12.2007, 20:33

Результатом должен быть путь из 9ти ребер (ребро г - 2 раза)
Ответить с цитированием
  (#22 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 03.12.2007, 23:49

Раз ребро "г" удвоилось, то теперь нечетную степень имеют только вершины 2 и 5. Поэтому такой путь можно искать только между ними. В программе, в основном, меняется только проверка принадлежности очередного ребра списку пройденных ребер:
Код:
domains
текущая = integer
ребро = ребро(string,integer,integer)
sl = string*
predicates
determ является_элементом(string,sl)
реверс(sl,sl,sl)
determ write1(integer,sl)
nondeterm найти_путь(integer,sl,sl,integer)
nondeterm дуга(string,integer,integer)
nondeterm ребро(string,integer,integer)
nondeterm эйлеров_путь(integer,sl)
determ проверка(string,sl)
clauses
дуга("а",1,2).
дуга("б",2,3).
дуга("в",1,3).
дуга("г",2,4).
дуга("д",2,5).
дуга("е",4,3).
дуга("ж",3,5).
дуга("з",4,5).

ребро(Ребро,Начало,Конец):-
    дуга(Ребро,Начало,Конец);
    дуга(Ребро,Конец,Начало).

реверс([А|П],С,Р):- реверс(П,[А|С],Р).
реверс([],П,П).

является_элементом(Ребро,[Ребро|_]):- !.
является_элементом(Ребро,[_|Пройденные]):-
    является_элементом(Ребро,Пройденные).

write1(В,[]):- write(В).
write1(В,[Ребро|A]):-
    ребро(Ребро,В,В1),
    !,
    writef("% - % - ",В,Ребро),
    write1(В1,A).

найти_путь(_,Путь,Путь,0):- !.
найти_путь(Текущая,Пройденные,Путь,Д):-
    ребро(Ребро,Текущая,Новая),
    проверка(Ребро,Пройденные),
    Д1 = Д - 1,
    найти_путь(Новая,[Ребро|Пройденные],Путь,Д1).

проверка(Ребро,Пройденные):- Ребро<>"г", !,
    not(является_элементом(Ребро,Пройденные)).
проверка(Г,[Г|Пройденные]):- !,
    not(является_элементом(Г,Пройденные)).
проверка(Г,[_|Пройденные]):- проверка(Г,Пройденные).
проверка(_,[]).

эйлеров_путь(Вершина,Путь):-
    найти_путь(Вершина,[],Путь1,9),
    реверс(Путь1,[],Путь),
    nl,
    write1(Вершина,Путь).
goal
эйлеров_путь(2,Путь),nl.
Решений теперь 104. Первым находится такое:
Код:
2 - б - 3 - ж - 5 - д - 2 - г - 4 - е - 3 - в - 1 - а - 2 - г - 4 - з - 5
Путь=["б","ж","д","г","е","в","а","г","з"]
Ответить с цитированием
  (#23 (permalink)) Старый
Stom Stom вне форума
Новичок
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2007
Post 20.12.2007, 21:45

Alison спасибо огромное - все работает
Ответить с цитированием
  (#24 (permalink)) Старый
Stom Stom вне форума
Новичок
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2007
Post 20.12.2007, 21:45

Alison спасибо огромное - все работает
Ответить с цитированием
Ads
  (#25 (permalink)) Старый
Stom Stom вне форума
Новичок
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2007
Post 20.12.2007, 21:45

Alison спасибо огромное - все работает
Ответить с цитированием
Ads
Ответ

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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Интересная проблема kostyanisha Любые вопросы от новичков 1 16.02.2012 21:06
Интересная проблема Kirill Mashtaler Процессоры 10 12.01.2012 18:10
интересная программа evgen1 Pascal 15 15.12.2010 20:49
интересная задача n-andriy Pascal 3 24.06.2010 12:04
Интересная программа.... jkwe45 Софт и программы 2 15.02.2010 14:25
Интересная задачка hasper Prolog 35 21.12.2009 21:12
Интересная задачка DYX_56 Pascal 7 10.09.2008 21:04
Интересная проблема с ХР vitem Софт и программы 13 14.07.2008 10:55
Интересная задачка =) Gateway Prolog 5 25.01.2008 03:07
Интересная задача!!!!! С ++ eugene С/С++ 0 23.06.2007 18:24
Интересная задачка Black Monarh Pascal 6 28.12.2006 21:55
Интересная задача как создать алгоритм данных на вычисление ЕкатеринаАК Алгоритмы 8 06.12.2005 12:07



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