Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Нужна помощь в решении задачи 
V
    Опции темы
LFC
Дата 22.12.2008, 18:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 18.12.2008

Репутация: нет
Всего: нет



Почему у меня в этой программе выдается ошибка? Подскажите пожайлуста где и как исправить.

Сделала программу на Прологе, определяющую эйлеровый путь, начинающийся с заданной вершины в неориентированном графе.
Путь называется эйлеровым, если проходит через все ребра графа по одному разу.
Теорема Эйлера утверждает, что такой путь всегда существует, если количество вершин в графе с нечетной степенью равно 0 или 2.
Степень вершины – это количество ребер, которые инцидентны данной вершине.
Если количество вершин с нечетной степенью равно 2, то эйлеровый путь всегда начинается в одной из таких вершин.

global domains

  file = input
  path = integer*
  vector = integer*

predicates

readgraph( symbol, vector, vector, vector ) %чтение графа
readgraph2( vector, vector, vector, vector )
find( vector, vector, vector, vector, path ) %поиск эйлерова пути
find2( integer, vector, vector, vector, vector, path, path )
find3( integer, vector, vector, vector, vector, path, path, integer )
store( vector, vector, vector, vector )
addpath( path, path, integer ) %добавление цепочек
append( path, path, path )
append( path, path )
addpathpath( path, path, path )
findpath( vector, vector, path, path )
notempty( vector ) %проверка есть ли еще необработанные вершины
empty( vector )
extractto( path, integer, path )
extractfrom( path, integer, path )
createcounter( vector, integer, integer ) %количество графов в вершинах
incv( vector, integer, integer, vector ) 
verify(vector) %проверяет можно ли построить путь эйлера

clauses

createcounter( [], I, N ):- %создаем считчик вершин
  I = N, !.
createcounter( [H|T], I, N ):-
  I < N,
  H = 0,
  I2 = I + 1, 
  createcounter( T, I2, N ), !.

incv( [], _, _, [] ):- !. %увеличение количества вершин
incv( [H|T], I, V, [H1|T1] ):-
  I = V,
  H1 = H + 1,
  I2 = I + 1,
  incv( T,  I2, V, T1 ), !.  
incv( [H|T], I, V, [H1|T1] ):-
  I <> V,
  H1 = H,
  I2 = I + 1,
  incv( T,  I2, V, T1 ), !.

readgraph( FileName, V1, V2, Counter ):- %чтение графа
  openread( input, FileName ),
  readdevice(input),
  readint(N),
  createcounter( Temp, 0, N ),
  readgraph2( V1, V2, Temp, Counter ), !.

readgraph2( [], [], Temp, Counter ):-
  eof(input),
  Counter = Temp, !.  
readgraph2( [H1|T1], [H2|T2], Counter, Counter2 ):-
  readln(_),
  readint(V1),
  readint(V2),
  H1 = V1,
  H2 = V2,
  incv( Counter, 0, V1, Temp ),
  incv( Temp, 0, V2, Temp2 ),
  readgraph2( T1, T2, Temp2, Counter2 ), !.

append( [], L, L ). %добавление списков в список
append( [H|L1], L2, [H|L3] ):-
  append( L1, L2, L3 ).
addpath( PIn, POut, V ):-
  append( PIn, [V], POut ).
  
append( [], [] ):- !.
append( [H1|T1], [H2|T2] ):-
  H2 = H1,
  append( T1, T2 ), !.  
  
extractto( [], _, [] ):- !. %извлечение списка до определенного значения
extractto( [H1|_], Val, [H2|T2] ):-
  H1 = Val,
  H2 = H1,
  T2 = [], !.
extractto( [H1|T1], Val, [H2|T2] ):-
  H1 <> Val,
  H2 = H1,
  extractto( T1, Val, T2 ), !.

extractfrom( [], _, Out ):- %извлечение списка после определенного значения
  Out = [], !.
extractfrom( [H1|T1], Val, Out ):-
  H1 <> Val,
  extractfrom( T1, Val, Out ), !.
extractfrom( [H1|T1], Val, Out ):-
  H1 = Val,
  append( T1, Out ), !.

addpathpath( [], P2, P3 ):-
  P3 = P2, !.
addpathpath( P1, [H|T], P3 ):-
  extractto( P1, H, Temp1 ),
  extractfrom( P1, H, Temp2 ),
  append( Temp1, T, Temp3 ),
  append( Temp3, Temp2, P3 ), !.

find( [IH1|IT1], [IH2|IT2], [OH1|OT1], [OH2|OT2], P ):- %поиск пути
  IH1 < 0,
  OH1 = IH1,
  OH2 = IH2,
  find( IT1, IT2, OT1, OT2, P ), !.  
find( [IH1|IT1], [IH2|IT2], [OH1|OT1], [OH2|OT2], P ):-
  IH1 >= 0,
  addpath( [], Temp, IH1 ),
  OH1 = -1,
  OH2 = -1,
  find2( IH2, IT1, IT2, OT1, OT2, Temp, P ), !.
find2( -1, VIn1, VIn2, VOut1, VOut2, PIn, POut ):-
  VOut1 = VIn1,
  VOut2 = VIn2,
  POut = PIn, !.
find2( V, VIn1, VIn2, VOut1, VOut2, PIn, POut ):-
  find3( V, VIn1, VIn2, Temp1, Temp2, PIn, Temp3, Cont ),
  find2( Cont, Temp1, Temp2, VOut1, VOut2, Temp3, POut ), !.
find3( V, [IH1|IT1], [IH2|IT2], [OH1|OT1], [OH2|OT2], PIn, POut, Cont ):-
  V <> IH1,
  OH1 = IH1,
  OH2 = IH2,
  find3( V, IT1, IT2, OT1, OT2, PIn, POut, Cont ), !.
find3( V, [IH1|IT1], [IH2|IT2], [OH1|OT1], [OH2|OT2], PIn, POut, Cont ):-
  V = IH1,
  addpath( PIn, Pout, V ),
  Cont = IH2,  
  OH1 = -1,
  OH2 = -1,
  store( IT1, IT2, OT1, OT2 ), !.
find3( V, [], [], [], [], PIn, POut, Cont ):-
  addpath(  PIn, POut,  V ),
  Cont = -1, !.

store( [], [], [], [] ):- !.
store( [IH1|IT1], [IH2|IT2], [OH1|OT1], [OH2|OT2] ):-
  OH1 = IH1,
  OH2 = IH2,
  store( IT1, IT2, OT1, OT2 ), !.

notempty( [H|_] ):-
  H >= 0, !.
notempty( [H|T] ):-
  H < 0,
  notempty(T), !.

empty( [] ):- !.  
empty( [H|T] ):-
  H < 0,
  empty(T), !.
  
findpath( V1, _, PIn, POut ):-
  empty(V1),
  POut = PIn, !.
findpath( V1, V2, PIn, POut ):-
  notempty(V1),
  find( V1, V2, NewV1, NewV2, NewP ),
  addpathpath( PIn, NewP, NewP2 ), 
  findpath( NewV1, NewV2, NewP2, POut ), !.

verify([]):- !.
verify( [H|_] ):-
  I = H mod 2,
  I = 1,
  write( "graph nevozmogen" ), !.
verify( [H|T] ):-
  I = H mod 2,
  I = 0,
  verify(T), !.
  
goal

  readgraph( "graph.txt", V1, V2, Counter ), %читаем граф из файла
  verify(Counter), %проверяем на возможность создания єйлерова пути
  findpath( V1, V2, [], P ), %ищем этот путь
  write(P), %печатаем
  readdevice(stdin),
  
  readchar(_).
  
PM MAIL   Вверх
aga
Дата 23.12.2008, 19:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 5
Регистрация: 29.11.2008

Репутация: нет
Всего: нет



что-то многовато вы наворочали -- должно быть гораздо проще... вывалите, пожалуйста, конкретный граф...
PM MAIL   Вверх
LFC
Дата 24.12.2008, 14:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 18.12.2008

Репутация: нет
Всего: нет



Цитата(aga @ 23.12.2008,  19:09)
что-то многовато вы наворочали -- должно быть гораздо проще... вывалите, пожалуйста, конкретный граф...

Как можно проще? Если можно напиши как именно. Я плохо разбираюсь в прологе.
PM MAIL   Вверх
aga
Дата 24.12.2008, 15:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 5
Регистрация: 29.11.2008

Репутация: нет
Всего: нет



DOMAINS     s=symbol  sl=s*

DATABASE
          point(s)

PREDICATES
          makePoints(sl)
          graph(sl)
     eylerWay(s,sl,sl)   step(s,sl,s,sl)   rebro(sl,s,s,sl)        
          writeWay(sl)
CLAUSES

eylerWay(_,[],[]):-!.
eylerWay(Fr,Gr,[To|H]):- step(Fr,Gr,To,Gnew), eylerWay(To,Gnew,H).

step(Fr,Gr,To,Gnew):- rebro(Gr,Fr,To,Gnew).
step(Fr,Gr,To,Gnew):- rebro(Gr,To,Fr,Gnew).

rebro([X|[Y|Z]],X,Y,Z).
rebro([X|[Y|Z]],A,B,[X|[Y|H]]):- rebro(Z,A,B,H).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

graph([a,b,a,e,e,b,b,c,c,d,d,a]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

makePoints([]):-!.
makePoints([G|H]):- point(G),!, makePoints(H).
makePoints([G|H]):- !, assert(point(G)), makePoints(H).

writeWay([]):-!.
writeWay([G|H]):- write(" -> ",G), !, writeWay(H).

GOAL
 clearwindow, graph(Gr), makePoints(Gr),
              
     point(Start), nl, write("from ",Start, "   **************"),

          eylerWay(Start,Gr,Way), nl, writeWay(Way), fail.


правда, "не из заданной вершины", а перебирает все...

graph([a,b,a,e,e,b,b,c,c,d,d,a]). -- конверт так называемый...

eylerWay(s,  --  вершина, из которой выходит
               sl,  --  граф в виде списка
               sl)  --  возвращаемый путь...

Добавлено через 4 минуты и 31 секунду
и такой вот выход...
from a   **************
 -> b -> c -> d -> a -> e -> b
 -> b -> e -> a -> d -> c -> b
 -> e -> b -> c -> d -> a -> b
 -> e -> b -> a -> d -> c -> b
 -> d -> c -> b -> a -> e -> b
 -> d -> c -> b -> e -> a -> b
from b   **************
 -> c -> d -> a -> b -> e -> a
 -> c -> d -> a -> e -> b -> a
 -> a -> e -> b -> c -> d -> a
 -> a -> d -> c -> b -> e -> a
 -> e -> a -> b -> c -> d -> a
 -> e -> a -> d -> c -> b -> a
from e   **************
from c   **************
from d   **************

PM MAIL   Вверх
LFC
Дата 24.12.2008, 16:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 18.12.2008

Репутация: нет
Всего: нет



Цитата(aga @ 24.12.2008,  15:19)
DOMAINS     s=symbol  sl=s*

DATABASE
          point(s)

PREDICATES
          makePoints(sl)
          graph(sl)
     eylerWay(s,sl,sl)   step(s,sl,s,sl)   rebro(sl,s,s,sl)        
          writeWay(sl)
CLAUSES

eylerWay(_,[],[]):-!.
eylerWay(Fr,Gr,[To|H]):- step(Fr,Gr,To,Gnew), eylerWay(To,Gnew,H).

step(Fr,Gr,To,Gnew):- rebro(Gr,Fr,To,Gnew).
step(Fr,Gr,To,Gnew):- rebro(Gr,To,Fr,Gnew).

rebro([X|[Y|Z]],X,Y,Z).
rebro([X|[Y|Z]],A,B,[X|[Y|H]]):- rebro(Z,A,B,H).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

graph([a,b,a,e,e,b,b,c,c,d,d,a]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

makePoints([]):-!.
makePoints([G|H]):- point(G),!, makePoints(H).
makePoints([G|H]):- !, assert(point(G)), makePoints(H).

writeWay([]):-!.
writeWay([G|H]):- write(" -> ",G), !, writeWay(H).

GOAL
 clearwindow, graph(Gr), makePoints(Gr),
              
     point(Start), nl, write("from ",Start, "   **************"),

          eylerWay(Start,Gr,Way), nl, writeWay(Way), fail.


правда, "не из заданной вершины", а перебирает все...

graph([a,b,a,e,e,b,b,c,c,d,d,a]). -- конверт так называемый...

eylerWay(s,  --  вершина, из которой выходит
               sl,  --  граф в виде списка
               sl)  --  возвращаемый путь...

Добавлено @ 15:23
и такой вот выход...
from a   **************
 -> b -> c -> d -> a -> e -> b
 -> b -> e -> a -> d -> c -> b
 -> e -> b -> c -> d -> a -> b
 -> e -> b -> a -> d -> c -> b
 -> d -> c -> b -> a -> e -> b
 -> d -> c -> b -> e -> a -> b
from b   **************
 -> c -> d -> a -> b -> e -> a
 -> c -> d -> a -> e -> b -> a
 -> a -> e -> b -> c -> d -> a
 -> a -> d -> c -> b -> e -> a
 -> e -> a -> b -> c -> d -> a
 -> e -> a -> d -> c -> b -> a
from e   **************
from c   **************
from d   **************

спасибо, теперь понятно
PM MAIL   Вверх
Katyuska
Дата 4.5.2009, 17:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 27.4.2009

Репутация: нет
Всего: нет



Помогите пожалуйста решить задачу (на любом языке программирования)!!!
Заранее спасибо, Катерина!
Проектирование лексического анализатора


Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом ;(точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой (в обычной и логарифмической форме), знак присваивания (:=).

PM MAIL   Вверх
P4oLka
Дата 13.9.2009, 21:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 16
Регистрация: 16.8.2008

Репутация: нет
Всего: нет



Задача такого рода: Написать программу замены всех вхождений элемента в список на заданную константу. Пишем в Visual prolog 5.2. 
Все вхождения элемента ищутся так:

Код

domains 
list=integer*
constants 
a=8
predicates
member(integer,list)
clauses
member(Head,[Head|_]).
member(Head,[_|Tail]):-member(Head,Tail).
Goal 
member(a,[1,2,3,4,8]).


А вот с тем, как сделать замену, не совсем ясно. Подскажите пожалуйста.



Это сообщение отредактировал(а) P4oLka - 13.9.2009, 21:29
PM MAIL ICQ   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума Prolog
Void
  • Пожалуйста, создавайте темы с содержательными названиями.
  • Уважаемые учащиеся, здесь всегда рады помочь Вам, но не делать за Вас вашу работу. У вас гораздо больше шансов получить помощь, если Вы приложите усилия и поделитесь с нами проблемами и результатами. В противном случае добро пожаловать в раздел Центр Помощи.
  • Получив ответ на интересующий Вас вопрос, не забудьте пометить его как решённый.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Void.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Prolog | Следующая тема »


 




[ Время генерации скрипта: 0.1064 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.