VPF::[Prolog] Добрые люди, помогите - Форум программистов

Micher

Дата 15.12.2006, 18:15 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 129
Регистрация: 13.1.2006
Где: г. Ижевск

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

Люди добрые, очень нужно решить задачи. Времени на изучение совсем нет.
Может кто-то знает решения, или уже имеет готовые, отзовитесь. Очень нужна ваша помощь!

1) Дан ориентированный граф. Каждая вершина нагружена числом (стоимость
прохождения через вершину). Необходимо найти самый
кооткий путь (между заданными вершинами),
стоимость которого не превышает указанной суммы.

2) Алеша, Боря, Гриша нашли в земле сосуд.
Алеша предположил, что это греческий сосуд 5 века,
Боря, что сосуд финский 3 века,
Гриша - не греческий 4 века.
Каждый мальчик прав только в одном случае.

3) На вход подается список целых чисел. Построить из них
бинарное дерево (если это возможно), обладающее
следующим свойством: корень любого поддерева является
суммой чисел, находящихся на узлах непосредственных

Guedda

Дата 16.12.2006, 09:40 (ссылка)

(нет голосов)

Загрузка ...

Подрывник

Профиль
Группа: Завсегдатай
Сообщений: 3137
Регистрация: 27.12.2005
Где: Ростов-на-Дону

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

Модератор: Пожалуйста, один топик - один вопрос.

--------------------

Ll 2

Artemios

Дата 17.12.2006, 01:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

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

Цитата(Micher @ 15.12.2006, 18:15

)

2) Алеша, Боря, Гриша

Код


только_один(А,Б):-
    А, not(Б);
    not(А), Б.

сосуд(Страна,Век):-
    member(Страна,[греческий,финский]),
    member(Век,[3,4,5]),
    только_один(Страна==греческий, Век==5), %Алеша
    только_один(Страна==финский, Век==3),   %Боря
    только_один(Страна\=греческий, Век==4). %Гриша

Проверка:

Цитата

?- сосуд(Страна,Век).

Страна = финский
Век = 5

Yes
?-

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Artemios

Дата 17.12.2006, 05:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

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

Цитата(Micher @ 15.12.2006, 18:15

)

1) Дан ориентированный граф.

Код


вершина(а,1).
вершина(б,2).
вершина(в,3).
вершина(г,4).
вершина(д,5).
вершина(е,6).
ребро(а,б).
ребро(а,в).
ребро(б,г).
ребро(б,в).
ребро(б,д).
ребро(в,г).
ребро(в,д).
ребро(г,е).
ребро(д,г).
ребро(д,е).

путь1(А,[А|Путь],[А|Путь]).
путь1(А,[Б|Путь1],Путь):-
    ребро(В,Б),
    not(member(В,Путь1)),
    путь1(А,[В,Б|Путь1],Путь).

цена([],0).
цена([А|Путь],Ц):-
    вершина(А,Ц1),
    цена(Путь,Ц2),
    Ц is Ц1+Ц2.

путь(А,Б,МаксЦена,Путь,Длина):-
    путь1(А,[Б],Путь),
    length(Путь,Длина),
    цена(Путь,Цена),
    Цена=<МаксЦена.

сравнение([Путь,Длина],[_,Длина1],[Путь,Длина]):- Длина<Длина1.
сравнение([_,Длина1],[Путь,Длина],[Путь,Длина]):- Длина=<Длина1.

поиск_мин_путь([[П,Д]],[П,Д]).
поиск_мин_путь([[П1,Д1]|Остальные],[П,Д]):-
    поиск_мин_путь(Остальные,[П2,Д2]),
    сравнение([П1,Д1],[П2,Д2],[П,Д]).

минимальный_путь(А,Б,МаксЦена,Путь):-
    findall([П,Д],путь(А,Б,МаксЦена,П,Д),СписокПар),
    поиск_мин_путь(СписокПар,[Путь,_]).

используем:

Цитата

?- минимальный_путь(а,е,15,Путь).

Путь = [а, в, д, е]

Yes
?- минимальный_путь(а,е,14,Путь).

Путь = [а, б, д, е]

Yes
?- минимальный_путь(а,е,13,Путь).

Путь = [а, б, г, е]

Yes
?- минимальный_путь(а,е,12,Путь).

No
?-

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Micher

Дата 20.12.2006, 09:08 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 129
Регистрация: 13.1.2006
Где: г. Ижевск

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

Artemios, я так понимаю решение для 6 вершин только. А возможно ли решение с неограниченным числом вершин графа?

skyboy

Дата 20.12.2006, 10:10 (ссылка)

(нет голосов)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

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

Цитата(Micher @ 20.12.2006, 08:08

)

Artemios, я так понимаю решение для 6 вершин только.

мне кажется, ты ошибаешься.

Artemios

Дата 20.12.2006, 10:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

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

Цитата(Micher @ 20.12.2006, 09:08

)

Artemios, я так понимаю решение для 6 вершин только. А возможно ли решение с неограниченным числом вершин графа?

Решение -- для произвольного числа вершин и ребер, заданного фактами с предикатами "вершина" и "ребро". В принципе, весь граф можно было подавать на вход, например парой списков, а в правилах делать разбор этих списков. Либо организовать диалог с пользователем с динамическим добавлением фактов в базу данных...

P.S.
Кстати, я тут подумал, что с программистской точки зрения правило "цена" лучше переписать так:

Код


цена([],Ц,Ц).
цена([А|Путь],Ц1,Ц):-
    вершина(А,Ц2),
    Ц3 is Ц1+Ц2,
    цена(Путь,Ц3,Ц).
цена(Путь,Цена):- цена(Путь,0,Цена).

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Artemios

Дата 20.12.2006, 11:34 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

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

P.P.S.
А также для "поиск_мин_путь":

Код


поиск_мин_путь([],[П,Д],[П,Д]).
поиск_мин_путь([[П1,Д1]|Остальные],[П2,Д2],[П,Д]):-
  сравнение([П1,Д1],[П2,Д2],[П3,Д3]),
  поиск_мин_путь(Остальные,[П3,Д3],[П,Д]).
поиск_мин_путь([[П1,Д1]|СписокПар],[П,Д]):-
  поиск_мин_путь(СписокПар,[П1,Д1],[П,Д]).

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Artemios

Дата 18.1.2007, 18:21 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

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

У меня Турбо нет, поэтому проверить все равно не смогу. Попробую дать общие рекомендации:
- переобозвать все предикаты и переменные (переменные -- с большой буквы которые) латинскими буквами
- буквы, используемые для имен вершин графа, заключить в кавычки
- в некоторых местах я использовал одинаковые имена для разных предикатов -- отличие по количеству аргументов -- их надо будет назвать по-разному (это предикаты цена и поиск_мин_путь в моих постах от 20.12.2006, 10:56 и 20.12.2006, 11:34)
- все написанные мной факты и правила заключить в секцию clauses
- перед секцией clauses поместить секцию predicates, в которой описать типизацию каждого используемого предиката, то есть описать типы аргументов для каждого предиката (здесь у тебя будут использоваться целые, строки, списки строк, списки списков строк), составные типы надо перед этой секцией описать в секции domains, например:

Цитата

DOMAINS
slist = string* % списки строк
slist2 = slist* % списки списков строк

- после секции clauses поместить секцию goal, в которой пишется конечная цель, которой программа должна достигнуть, используя описанные выше правила, например я делал такую проверку:

Цитата

?- минимальный_путь(а,е,13,Путь).

Путь = [а, б, г, е]

Yes
?-

а тебе нужно будет что-то вроде такого:

Цитата

GOAL
minimal_path('a','e',13,Path), write(Path), nl.

Добавлено @ 18:23
Опа, модераторы уже удалили просьбу переписать на Турбо... smile

Это сообщение отредактировал(а) Artemios - 18.1.2007, 18:39

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Micher

Дата 18.1.2007, 22:44 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 129
Регистрация: 13.1.2006
Где: г. Ижевск

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

Цитата(Artemios @ 18.1.2007, 18:21)

Попробую дать общие рекомендации:
....

Вот, что у меня получилось после преобразований:

Код


predicates
nondeterm peak(string, integer)
nondeterm rib(string, string)


clauses
peak("a",1).
peak("b",2).
peak("c",3).
peak("d",4).
peak("e",5).
peak("f",6).
rib("a","b").
rib("a","c").
rib("b","d").
rib("b","c").
rib("b","e").
rib("c","d").
rib("c","e").
rib("d","f").
rib("e","d").
rib("e","f").

path1(A,[A|Path],[A|Path]).    
path1(A,[B|Path1],Path):-    
    rib(C,B),
    not(member(C,Path1)),    
    path1(A,[C,B|Path1],Path).    


price([],Pr,Pr).    
price([A|Path],Pr1,Pr):-
    peak(A,Pr2),
    Pr3 is Pr1+Pr2,
    price(Path,Pr3,Pr).

price2(Path,Price):- price(Path,0,Price).


path(A,B,MaxPrice,Path,Dlina):-    
    path1(A,[B],Path),    
    length(Path,Dlina),    
    price2(Path,Price),    
    Price=<MaxPrice.


compare([Path,Dlina],[_,Dlina1],[Path,Dlina]):- Dlina<Dlina1.
compare([_,Dlina1],[Path,Dlina],[Path,Dlina]):- Dlina=<Dlina1.


find_minimal_path([],[P,D],[P,D]).    
find_minimal_path([[P1,D1]|Other],[P2,D2],[P,D]):-    
  compare([P1,D1],[P2,D2],[P3,D3]),    
  find_minimal_path(Other,[P3,D3],[P,D]).    

find_minimal_path([[P1,D1]|SpisokPar],[P,D]):-
  find_minimal_path(SpisokPar,[P1,D1],[P,D]).


minimal_path(A,B,MaxPrice,Path):-    
    findall([P,D],path(A,B,MaxPrice,P,D),SpisokPar),    
    find_minimal_path(SpisokPar,[Path,_]).


goal
minimal_path("a","f",13,Path), write(Path); write("Path not found !").

Не очень мне ясно, как в predicates определить оставшиеся правила и факты. И, на сколько я помню, в Турбо Прологе нет предиката member. Помогите плиз, чуть чуть совсем осталось.

Artemios

Дата 19.1.2007, 02:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

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

Аяй, вспомнил, что у меня в списках встречаются разнотипные данные, что Турбо/Вижл Прологи не позволяют smile

Хотя, это легко поправимо, т.к. эти данные встречаются только в виде пары [Путь,Длина], вместо которой надо будет ввести какой-нибудь функтор, немножко подумаю и позже допишу.

Пока что member:

Код


member(X,[X|L]).
member(X,[Y|L]):-
    member(X,L).

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Artemios

Дата 19.1.2007, 03:11 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

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

Цитата(Artemios @ 19.1.2007, 02:12

)

разнотипные данные, что Турбо/Вижл Прологи не позволяют

это я прогнал smile

Все позволяется smile

. Выглядеть будет примерно следующим образом:

Код


DOMAINS 

slist = string*
comby = slist;integer
comblist = comby*
comblist2 = comblist*

PREDICATES

peak(string, integer)
rib(string, string)
path1(string,slist,slist)
price(slist,integer,integer)
price2(slist,integer)
path(string,string,integer,slist,integer)
compare(comblist,comblist,comblist)
find_minimal_path(comblist2,comblist,comblist)
find_minimal_path2(comblist2,comblist)
minimal_path(string,string,integer,slist)
member(string,slist)

также замени в 56 и 62 строках приведенного тобой выше кода имя предиката find_minimal_path на find_minimal_path2

И еще вопрос: а findall в Турбо есть?

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

sergejzr

Дата 19.1.2007, 03:28 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

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

Модератор: Название темы должно отражать ее суть!

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

Micher

Дата 19.1.2007, 09:48 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 129
Регистрация: 13.1.2006
Где: г. Ижевск

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

Цитата(Artemios @ 19.1.2007, 03:11)

Цитата(Artemios @ 19.1.2007, 02:12

)

разнотипные данные, что Турбо/Вижл Прологи не позволяют

это я прогнал smile

Все позволяется smile

. Выглядеть будет примерно следующим образом:

Код

...

Хорошо. Спасибо огромное! Сейчас всё подставлю. Что касается findall, то в Турбо Прологе он есть.

Micher

Дата 19.1.2007, 11:12 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 129
Регистрация: 13.1.2006
Где: г. Ижевск

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

Ругается на строку:

Код


34)   Pr3 is Pr1+Pr2

На Pr3, мол он не обьявлен. А что кстате значит is, может знак = лучше поставить?

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