Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Prolog] Добрые люди, помогите

Автор: Micher 15.12.2006, 18:15

Люди добрые, очень нужно решить задачи. Времени на изучение совсем нет. Может кто-то знает решения, или уже имеет готовые, отзовитесь. Очень нужна ваша помощь! 1) Дан ориентированный граф. Каждая вершина нагружена числом (стоимость прохождения через вершину). Необходимо найти самый  кооткий путь (между заданными вершинами),  стоимость которого не превышает указанной суммы. 2) Алеша, Боря, Гриша нашли в земле сосуд. Алеша предположил, что это греческий сосуд 5 века, Боря, что сосуд финский 3 века, Гриша - не греческий 4 века. Каждый мальчик прав только в одном случае. 3) На вход подается список целых чисел. Построить из них бинарное дерево (если это возможно), обладающее следующим свойством: корень любого поддерева является суммой чисел, находящихся на узлах непосредственных

Автор: Guedda 16.12.2006, 09:40

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

Автор: Artemios 17.12.2006, 01:41

Цитата(Micher @  15.12.2006,  18:15 ) 2) Алеша, Боря, Гриша Код только_один(А,Б):-     А, not(Б);     not(А), Б. сосуд(Страна,Век):-     member(Страна,[греческий,финский]),     member(Век,[3,4,5]),     только_один(Страна==греческий, Век==5), %Алеша     только_один(Страна==финский, Век==3),   %Боря     только_один(Страна\=греческий, Век==4). %Гриша Проверка: Цитата ?- сосуд(Страна,Век). Страна = финский Век = 5 Yes ?-

Автор: Artemios 17.12.2006, 05:32

Цитата(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 ?-

Автор: Micher 20.12.2006, 09:08

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

Автор: skyboy 20.12.2006, 10:10

Цитата(Micher @  20.12.2006,  08:08 ) Artemios, я так понимаю решение для 6 вершин только. мне кажется, ты ошибаешься.

Автор: Artemios 20.12.2006, 10:56

Цитата(Micher @  20.12.2006,  09:08 ) Artemios, я так понимаю решение для 6 вершин только. А возможно ли решение с неограниченным числом вершин графа?  Решение -- для произвольного числа вершин и ребер, заданного фактами с предикатами "вершина" и "ребро". В принципе, весь граф можно было подавать на вход, например парой списков, а в правилах делать разбор этих списков. Либо организовать диалог с пользователем с динамическим добавлением фактов в базу данных... P.S. Кстати, я тут подумал, что с программистской точки зрения правило "цена" лучше переписать так: Код цена([],Ц,Ц). цена([А|Путь],Ц1,Ц):-     вершина(А,Ц2),     Ц3 is Ц1+Ц2,     цена(Путь,Ц3,Ц). цена(Путь,Цена):- цена(Путь,0,Цена).

Автор: Artemios 20.12.2006, 11:34

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

Автор: Artemios 18.1.2007, 18:21

У меня Турбо нет, поэтому проверить все равно не смогу. Попробую дать общие рекомендации:  - переобозвать все предикаты и переменные (переменные -- с большой буквы которые) латинскими буквами  - буквы, используемые для имен вершин графа, заключить в кавычки  - в некоторых местах я использовал одинаковые имена для разных предикатов -- отличие по количеству аргументов -- их надо будет назвать по-разному (это предикаты цена и поиск_мин_путь  в моих постах от 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  Опа, модераторы уже удалили просьбу переписать на Турбо...

Автор: Micher 18.1.2007, 22:44

Цитата(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

Аяй, вспомнил, что у меня в списках встречаются разнотипные данные, что Турбо/Вижл Прологи не позволяют  Хотя, это легко поправимо, т.к. эти данные встречаются только в виде пары [Путь,Длина], вместо которой надо будет ввести какой-нибудь функтор, немножко подумаю и позже допишу. Пока что member: Код member(X,[X|L]). member(X,[Y|L]):-     member(X,L).

Автор: Artemios 19.1.2007, 03:11

Цитата(Artemios @  19.1.2007,  02:12 ) разнотипные данные, что Турбо/Вижл Прологи не позволяют это я прогнал  Все позволяется . Выглядеть будет примерно следующим образом: Код 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 в Турбо есть?

Автор: sergejzr 19.1.2007, 03:28

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

Автор: Micher 19.1.2007, 09:48

Цитата(Artemios @ 19.1.2007,  03:11) Цитата(Artemios @  19.1.2007,  02:12 ) разнотипные данные, что Турбо/Вижл Прологи не позволяют это я прогнал  Все позволяется . Выглядеть будет примерно следующим образом: Код ... также замени в 56 и 62 строках приведенного тобой выше кода имя предиката find_minimal_path на find_minimal_path2 И еще вопрос: а findall в Турбо есть? Хорошо. Спасибо огромное! Сейчас всё подставлю. Что касается findall, то в Турбо Прологе он есть.

Автор: Micher 19.1.2007, 11:12

Ругается на строку:    Код 34)   Pr3 is Pr1+Pr2 На Pr3, мол он не обьявлен. А что кстате значит is, может знак = лучше поставить?

Автор: Artemios 20.1.2007, 02:11

Знак = означает унификацию термов слева и справа от знака. А так как запись 2+3 например, это не вычисление числа 5, а всего лишь инфиксная запись терма +(2,3), то попытка унификации 2+3 = 5 приведет к неуспеху (разные термы). is используется там, где нужно унифицировать арифметические выражения предварительно вычислив их. Но это все в общепринятом стандарте Пролога (ISO), который Турбо не поддерживает, следовательно могут быть и разночтения (я Турбой никогда не интересовался, соответственно и всех его особенностей не знаю) -- попробуй поставить = вместо is и скажешь, что получилось

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)