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

Всем привет!

Нужна помощ по деревьям (bynary trees):

Прога должна распознавать 2 типа деревьев:

up_zz:
1. либо пустое дерево
2. либо T=t(Left,Root,Right) так что:
Left and Right - типа down_zz
и все числа в дереве Left меньше Root
а все числа в дереве Right больше Root

down_zz:
1. либо пустое дерево
2. либо T=t(Left,Root,Right) так что:
Left and Right - типа up_zz
и все числа в дереве Left больше Root
а все числа в дереве Right меньше Root


Сказать по правде я пролог вижу второй раз в жизни, но вот кое что наваял, и ессесно - не работает.

Код:
up_zz(t(_,nil,_)):-!.
up_zz(t(Left,Root,Right)) :-    down_zz(t(_,Left,_)), 
                down_zz(t(_,Right,_)), 
                max_t(t(_,Left,_),Root,Root), 
                min_t(t(_,Right,_),Root,Root).

down_zz(_,nil,_):-!.
down_zz(t(Left,Root,Right)) :-     up_zz(t(_,Left,_)), 
                up_zz(t(_,Right,_)), 
                min_t(t(_,Left,_),Root,Root), 
                max_t(t(_,Right,_),Root,Root).

max_t(t(_,nil,_),X,X) :- !.
max_t(t(nil,A,nil),X,Max) :- max_num(A,X,Max),!.
max_t(t(Left,Root,Right),X,Res) :- max_t(t(_,Left,_),Root,Res1), 
                 max_t(t(_,Right,_),Root,Res2),
                 max_num(Res1,Res2,Res3),
                 max_num(Res3,X,Res).


min_t(t(_,nil,_),X,X) :- !.
min_t(t(nil,A,nil),X,Min) :- min_num(A,X,Min),!.
min_t(t(Left,Root,Right),X,Res) :- min_t(t(_,Left,_),Root,Res1), 
                 min_t(t(_,Right,_),Root,Res2),
                 min_num(Res1,Res2,Res3),
                 min_num(Res3,X,Res).

max_num(X,Y,X) :- X>Y,!.
max_num(_,Y,Y).

min_num(X,Y,Y) :- Y<X, !.
min_num(X,_,X).
Ответить с цитированием
  (#2 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 16.12.2007, 14:12

Если переписать буквально правила, что Вы написали для распознавания деревьев, на Пролог, то будет так:
Код:
up_zz(empty).
up_zz(t(Left,Root,Right)):-
    down_zz(Left),
    down_zz(Right),
    less(Left,Root),
    greater(Right,Root).

down_zz(empty).
down_zz(t(Left,Root,Right)):-
    up_zz(Left),
    up_zz(Right),
    greater(Left,Root),
    less(Right,Root).

less(empty,_).
less(t(Left,V,Right),Root):- 
    V < Root, 
    less(Left,Root),
    less(Right,Root).

greater(empty,_).
greater(t(Left,V,Right),Root):- 
    V > Root, 
    greater(Left,Root),
    greater(Right,Root).
Ответить с цитированием
  (#3 (permalink)) Старый
leonkes leonkes вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию 17.12.2007, 23:19

Спасибо, но почему-то работает не правильно...

Пример:

?- up_zz(t(15,10,t(6,8,nil))).
no

Это правильно...

?- down_zz(t(15,10,t(6,8,nil))).
no
А вот это нет...

И ещё вопрос - в вашей программе проверка на Root или на все елементы дерева?
Ответить с цитированием
  (#4 (permalink)) Старый
ponchik ponchik вне форума
Member
 
Сообщений: 24
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.12.2007
По умолчанию 18.12.2007, 01:04

Цитата:
Спасибо, но почему-то работает не правильно...

Пример:

?- up_zz(t(15,10,t(6,8,nil))).
no

Это правильно...

?- down_zz(t(15,10,t(6,8,nil))).
no
А вот это нет...

И ещё вопрос - в вашей программе проверка на Root или на все елементы дерева?
У тебя неправильный инпут.

например:
t(6,8,nil) - неверно.
t(t(nil,6,nil), 8, nil) - верно.
Ответить с цитированием
  (#5 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 18.12.2007, 18:30

Да, при этом в коде не nil, а empty.
Цитата:
?- up_zz(t(15,10,t(6,8,nil))).
no

Это правильно...

?- down_zz(t(15,10,t(6,8,nil))).
no
А вот это нет...
Если термы записать правильно, то отвечает в первом случае no, а во втором yes.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
leonkes leonkes вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию 18.12.2007, 21:27

Спасибо
Ответить с цитированием
Ads
  (#7 (permalink)) Старый
leonkes leonkes вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию 18.12.2007, 21:27

Спасибо
Ответить с цитированием
  (#8 (permalink)) Старый
leonkes leonkes вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию 18.12.2007, 21:27

Спасибо
Ответить с цитированием
Ответ

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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вопрос SSD Nicko Накопители 62 16.02.2012 18:49
Вопрос OoAa Любые вопросы от новичков 4 28.01.2012 23:23
Вопрос Владислав97 Видеокарты 4 22.01.2012 20:19
Вопрос nimens Любые вопросы от новичков 2 21.12.2011 01:00
Вопрос Ruslannn Видеокарты 2 28.11.2011 15:30
Вопрос froot1s Материнские платы 19 23.11.2011 00:32
Задачка по бинарным деревьям Евгений0110 Prolog 3 07.10.2011 23:32
вопрос desazr Сетевые подключения 1 23.03.2011 20:19
Вопрос по БП. Джаспер Блоки питания 3 19.02.2011 00:41
Вопрос о БП? механоид Видеокарты 8 14.01.2011 00:18
2 задачи по деревьям и строкам Deeller Prolog 4 05.06.2010 15:02
Вопрос про Msi p6n DART Подбор комплектующих 1 16.07.2008 07:00



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