Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Самая длинная ветка в дереве (наверное)
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Yusuke Yusuke вне форума
Новичок
 
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 29.11.2004
По умолчанию Самая длинная ветка в дереве (наверное) - 15.12.2004, 19:07

(турбо пролог)
Люди добрые, помогите написать процедуру.
Дано дерево (пусть "D2")
нужно пройти в глубену, и выписать значения вершин пути (от корня до глубени)

Пример:
20
/
12 25
/ /
10 17 23 68
/
22

(Путь:20,25,23,22)


Зарание огромное спасибо.
Ответить с цитированием
  (#2 (permalink)) Старый
DaoDizzy DaoDizzy вне форума
Member
 
Сообщений: 58
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.02.2004
По умолчанию 16.12.2004, 18:16

Два и 6 сотых раза перечитал и ничего не понял при чем там Д2 - не не понял - поясни пожалуйста (хотя, может я один не понял...)
Ответить с цитированием
  (#3 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 16.12.2004, 18:18

Я тоже честно говоря не понял, что такое глубень?
Ответить с цитированием
  (#4 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,955
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 18.12.2004, 16:01

Вот прога, определяющая самую длинную ветку в дереве:
Код:
domains 
Дерево = n;t(integer,Дерево,Дерево)
Ветка = integer*
predicates
nondeterm макс_ветка(Дерево,Ветка)
nondeterm ветка(Дерево,Ветка)
nondeterm больше(Дерево,Ветка)
длиннее(Ветка,Ветка)
goal 
Дерево = t(20,t(12,t(10,n,n),t(17,n,n)),t(25,t(23,t(22,n,n),n),t(68,n,n))),
макс_ветка(Дерево,Ветка),write(Ветка).
clauses
макс_ветка(Дерево,Ветка):-ветка(Дерево,Ветка),
   not(больше(Дерево,Ветка)).

ветка(t(Верш,Лев,_),[Верш|Ветка]):-ветка(Лев,Ветка).
ветка(t(Верш,_,Прав),[Верш|Ветка]):-ветка(Прав,Ветка).
ветка(n,[]).

больше(Дерево,Ветка):-ветка(Дерево,Ветка1),длиннее(Ветка1,Ветка).

длиннее([_|Ветка1],[_|Ветка]):-длиннее(Ветка1,Ветка).
длиннее([_|_],[]).
Результат:
Код:
Ветка=[20,25,23,22]
Ответить с цитированием
  (#5 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 18.12.2004, 23:19

Вот еще один вариантик того же
Код:
domains
Дерево = n;t(integer,Дерево,Дерево)
Ветка = integer*
predicates
nondeterm макс_ветка(Дерево,integer,Ветка)
глубина(Дерево,integer)
макс(integer,integer,integer)
goal
Дерево = t(20,t(12,t(10,n,n),t(17,n,n)),t(25,t(23,t(22,n,n),n),t(68,n,n))),
глубина(Дерево,Глубина),
макс_ветка(Дерево,Глубина,Ветка),write(Ветка).
clauses
макс_ветка(n,-1,[]).
макс_ветка(t(Верш,Лев,_),K,[Верш|Ветка]):- K>-1,K1=K-1,
    макс_ветка(Лев,K1,Ветка).
макс_ветка(t(Верш,_,Прав),K,[Верш|Ветка]):- K>-1,K1=K-1,
    макс_ветка(Прав,K1,Ветка).

глубина(n,-1).
глубина(t(_,Лев,Прав),K):- глубина(Лев,K1),глубина(Прав,K2),
    макс(K1,K2,M),K=M+1.
    
макс(A,B,A):- A>=B,!.
макс(_,B,B).
Результат, естественно, тот же.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,955
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 19.12.2004, 00:01

Ну уж если соревноваться, то вот, держи гранату (в два предиката):
Код:
domains 
Дерево = n;t(integer,Дерево,Дерево) 
Ветка = integer* 
predicates 
nondeterm глубина(Дерево,Ветка,integer) 
макс(Ветка,integer,Ветка,integer,Ветка,integer) 
goal 
Дерево = t(20,t(12,t(10,n,n),t(17,n,n)),t(25,t(23,t(22,n,n),n),t(68,n,n))), 
глубина(Дерево,Ветка,Глубина),write(Ветка,Глубина). 
clauses 
глубина(n,[],-1). 
глубина(t(Верш,Лев,Прав),[Верш|Ветка],Г):-
   глубина(Лев,Ветка1,Г1),глубина(Прав,Ветка2,Г2), 
   макс(Ветка1,Г1,Ветка2,Г2,Ветка,Г3),Г=Г3+1. 
   
макс(Ветка1,Г1,_,Г2,Ветка1,Г1):-Г1>Г2,!. 
макс(_,_,Ветка,Г,Ветка,Г).
А вот Бомба (одним предикатом):
Код:
domains 
Дерево = n;t(integer,Дерево,Дерево) 
Ветка = integer* 
predicates 
nondeterm глубина(Дерево,Ветка,integer) 
goal 
Дерево = t(20,t(12,t(10,n,n),t(17,n,n)),t(25,t(23,t(22,n,n),n),t(68,n,n))), 
глубина(Дерево,Ветка,Глубина),write(Ветка,Глубина). 
clauses 
глубина(n,[],-1). 
глубина(t(Верш,Лев,Прав),[Верш|Ветка],Г):-
   глубина(Лев,Ветка,Г1),глубина(Прав,_,Г2), 
   Г1>=Г2,!,Г=Г1+1.
глубина(t(Верш,_,Прав),[Верш|Ветка],Г):-
   глубина(Прав,Ветка,Г1),Г=Г1+1.
Кто напишет ещё лаконичнее (типа вообще без предикатов) ?

У меня вообще такое ощущение, что любую прогу можно уменьшить как минимум на один предикат :!: . Я об этом как-то писал Mnior-у во время одной из наших полемик.
Ответить с цитированием
  (#7 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 19.12.2004, 00:10

Винитарх, в жизни бы не стала с тобой соревноваться. .

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

Винитарх, ты не поверишь, но оба варианта в моих размышлениях возникали, но я от них отказалась только потому, что хотела найти все ветки максимальной длины. Ты здесь выкрутился за счет отсечений, а без них в решении появляются дупликаты в большом количестве, а я этого не люблю.
У нас и так в обеих исходных прогах решения выдавались по 2 раза.
Ответить с цитированием
  (#9 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 19.12.2004, 11:11

Винитарх, а если добиваться эффективности при нахождении всех самых длинных веток, то можно ли здесь чего-нибудь сделать и как?
Ответить с цитированием
  (#10 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,955
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 19.12.2004, 12:00

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

Ну, например, по быстродействию. Это, вообще, теперь актуальнее, чем по памяти, или нет? Лаконичность пока не будем брать в расчет.
Ответить с цитированием
  (#12 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,955
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 20.12.2004, 20:42

Я думаю, что эта прога достаточно быстрая и работает без дубликатов:
Код:
domains 
Дерево = n;t(integer,Дерево,Дерево) 
Ветка = integer* 
predicates 
nondeterm глубина(Дерево,Ветка,integer) 
макс(Ветка,integer,Ветка,integer,Ветка,integer) 
goal 
Дерево = t(20,t(12,t(10,n,n),t(17,n,n)),t(25,t(23,t(22,n,n),n),t(68,n,n))), 
глубина(Дерево,Ветка,Глубина),write(Ветка,Глубина). 
clauses 
глубина(n,[],-1). 
глубина(t(Верш,Лев,Прав),[Верш|Ветка],Г):- 
   глубина(Лев,Ветка1,Г1),глубина(Прав,Ветка2,Г2), 
   макс(Ветка1,Г1,Ветка2,Г2,Ветка,Г3),Г=Г3+1. 
    
макс(Ветка1,Г1,_,Г2,Ветка1,Г1):-Г1>Г2,!. 
макс(_,_,Ветка,Г,Ветка,Г).
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 20.12.2004, 21:03

Да, но она находит не все максимальные ветки, а одну. Речь идет о всех. Просто здесь в дереве из goal и так одна, а если б их было несколько?
Ответить с цитированием
  (#14 (permalink)) Старый
BLooDCorpse BLooDCorpse вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.10.2007
По умолчанию 05.12.2007, 17:35

Код:
domains
Дерево = n;t(integer,Дерево,Дерево)
Ветка = integer*
predicates
nondeterm глубина(Дерево,Ветка,integer)
goal
Дерево = t(20,t(12,t(10,n,n),t(17,n,n)),t(25,t(23,t(22,n,n),n),t(68,n,n))),
глубина(Дерево,Ветка,Глубина),write(Ветка,Глубина).
clauses
глубина(n,[],-1).
глубина(t(Верш,Лев,Прав),[Верш|Ветка],Г):-
  глубина(Лев,Ветка,Г1),глубина(Прав,_,Г2),
  Г1>=Г2,!,Г=Г1+1.
глубина(t(Верш,_,Прав),[Верш|Ветка],Г):-
  глубина(Прав,Ветка,Г1),Г=Г1+1.
Попробовал реализовать данный алгоритм на TurboProlog, в результате постоянно получаю ответ, равный -1. Подчёркивание тоже ничего не даёт. Не подскажете, как исправить сей алгоритм под TurboProlog?
Спасибо!
Ответить с цитированием
  (#15 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 05.12.2007, 17:45

Нужно аккуратно заменить русские буквы английскими, и все.
Ответить с цитированием
Ответ

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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
нужна ветка реестра a6shadow Любые вопросы от новичков 0 10.12.2011 03:43
Задача-Паскаль. Длинная арифметика. Ksuuu Pascal 1 24.05.2011 22:57
Длинная арифметика построение двух столбиков СтуденткаЯ Delphi 1 26.12.2010 20:19
Проблема с материнкой(наверное) Diamond Любые вопросы от новичков 8 23.12.2010 09:13
Наверное видеокарта.... :( troxin Любые вопросы от новичков 22 27.10.2010 21:17
Длинная пробельная строка Rocky Офтопик 44 07.03.2010 21:44
ХЗ как назвать. Наверное специфические загадки. night-stels Офтопик 25 29.08.2009 01:48
Есть ли в C# длинная арифметика Exmap .NET 5 05.08.2008 15:30
Новая ветка форума. Предложение. MaPuK О сайте и форуме 26 19.09.2007 15:44
Наверное я с ума схожу... Виталик 1 Офтопик 29 05.05.2007 05:25
Длинная строка символов без разделителей Anonymous PHP 1 15.12.2003 02:27



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