Подсчет всех четных целых чисел в b-дереве в Prolog

Question

Я хочу написать программу в Prolog, которая строит список всех четных целых чисел, которые находятся в b-дереве. Вот что я написал до сих пор. Предикат, который подсчитывает все элементы в дереве. Я не знаю, где поцарапать.

Domains 
element=integer 
tree=a(tree,element,tree);void 
    list=integer* 

Predicates 
    nondeterm count(tree,element) 
    nondeterm count_even(tree,list) 

Clauses 
    count(a(void,Number,void),1). 
count(a(Esq,_,Dreta),Counter) :- 
    count(Esq,Counter1), 
    count(Dreta,Counter2), 
    Counter=Counter1+Counter2+1. 

Goal 
     count(a(a(void,1,void),5,a(a(void,4,void),1,a(void,4,void))),N). 

Большое спасибо.

Answer 1

Незнайка ничего о Visual Prolog, но в обычном Прологе, я сделаю что-то вроде следующего ...

Во-первых, я бы обозначить пустой ВТКЕЕ как атом btree и представляют собой непустое ВТКЕЕ как структура арностью 3, таким образом:

btree(Payload, LeftChildren, RightChildren) 

, где Payload представляет данные для узла (целое число, по-видимому), с LeftChildren и RightChildren являясь btrees, представляющие, соответственно, левого и правого потомков текущего узла ,

Обход дерева для подсчета узлов с четными узлами прост. Общий предикат имеет arity 2, принимая структуру [bound] btree, подлежащую исследованию, и связанное или несвязанное значение, представляющее количество четных элементов. Он называет внутренний, рекурсивный «хелперный» предикат, который ходит по дереву и развивает счет.

count_even(T , N) :- count_even(T , 0 , N) . 

Внутренний предикат также прост. Имея arity 3, первый аргумент - это дерево, которое нужно изучить, второе - это аккумулятор, а третий - конечный счет (который не будет унифицирован до самого конца). Возможны два случая.

1. Если дерево пусто, то есть окончательный подсчет:

   count_even(btree , N , N) . 
   

2. Если дерево не пусто, мы рассматриваем текущий узел, а затем рекурсивно проходят левые и правые дочерние дерева , таким образом:

   count_even(btree(V , L , R) , T , N) :- 
       is_even(V , X) , 
       T1 is T+X , 
       count_even(L , T1 , T2) , 
       count_even(R , T2 , N ) 
       . 
   

нам также необходим тривиальный помощник, чтобы сказать нам о том, четном или нечетном конкретное значение:

is_even(V , 1) :- 0 is V mod 2 , ! . 
is_even(V , 0) . 

Следует отметить, что структура данных вы используете не б-дерево, само по себе: это бинарное дерево.

B-деревья - это нечто вроде обобщенного сбалансированного по высоте двоичного дерева, оптимизированного для хранения на диске. Каждый узел имеет переменное количество ключей и переменное количество детей (соответствующее количеству ключей).Для получения дополнительной информации см

• http://en.wikipedia.org/wiki/B-tree
• http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html
• http://www.dtic.upf.edu/~rramirez/TA/btrees.pdf

Вот картина B-дерева:

И картина двоичном Дерево:

Answer 2

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

element=integer 
tree=a(tree,element,tree);void 
    list=integer* 

Predicates 
    nondeterm count_even(tree,list) 

Clauses 
    count_even(a(void,Number,void),Value):- 
     Value = 1 - Number mod 2. 
count_even(a(Esq,Number,Dreta),Counter) :- 
    count_even(Esq,Counter1), 
    count_even(Dreta,Counter2), 
    count_even=Counter1 + Counter2 + 1 - Number mod 2. 

Я просто рассчитывать 1 - Number mod 2 что 1, если число четное и 0 в противном случае.