在 Prolog 中计算 b 树中的所有偶数

发布于 2024-12-24 02:33:54 字数 514 浏览 2 评论 0原文

我想在 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).

多谢。

原文

I want to write a program in Prolog that builds a list of all the even integers that reside in a b-tree.
This is what I've written so far. A predicate that counts all the elements in the tree. I don't know where to scratch.

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).

Thanks a lot.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

沉默的熊 2024-12-31 02:33:54

我不知道有关 Visual Prolog 的任何信息，但在正常的 Prolog 中，我会执行以下操作...

首先，我将空 btree 表示为原子 btree 并将非空 btree 表示为arity 3 的结构，因此：

btree( Payload, LeftChildren, RightChildren )

其中 Payload 是节点的数据（显然是一个整数），LeftChildren 和 RightChildren 是 btree分别表示当前节点的左子节点和右子节点。

遍历树来计算具有偶值节点的节点很简单。公共谓词的元数为 2，接受要检查的 [bound] btree 结构，以及表示偶数项计数的绑定或未绑定值。它调用一个内部递归“辅助”谓词来遍历树并开发计数。

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

内部谓词也很简单。数量为 3，第一个参数是要检查的树，第二个参数是累加器，第三个参数是最终计数（直到最后才会统一）。有两种可能的情况。

如果树是空的，我们就有最终的计数：
```
count_even( btree , N , N ) 。
```

如果树非空，我们检查当前节点，然后递归地遍历左右子树，因此：< /p>

count_even( btree( V , L , R ) , T , N ) :-
  is_even( V , X ) ,
  T1 是 T+X ，
  count_even( L , T1 , T2 ) ,
  count_even( R , T2 , N )
  。

我们还需要一个简单的助手来告诉我们特定值是偶数还是偶数odd：

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

应该注意的是，您使用的数据结构本身不是b树：它是一个二叉树。

B 树是针对磁盘存储优化的高度平衡二叉树的概括。每个节点都有可变数量的键和可变数量的子节点（对应于键的数量）。有关详细信息，请参阅

这是 B 树的图片：

B-Tree Visualization

以及二叉树的图片：

二叉树可视化

Dunno anything about Visual Prolog, but in normal Prolog, I'd do something like the following...

First, I'd denote an empty btree as the atom btree and represent a non-empty btree as a structure of arity 3, thus:

btree( Payload, LeftChildren, RightChildren )

where Payload is the data for the node (an integer apparently), with LeftChildren and RightChildren being the btrees representing, respectively, the left and right children of the current node.

Traversing the tree to count those nodes with even-valued nodes is simple. The public predicate has arity 2, accepting the [bound] btree structure to be examined, and a bound or unbound value representing the count of even items. It calls an internal, recursive "helper" predicate that walks a tree and develops the count.

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

The internal predicate is simple as well. Having arity 3, the first argument is the tree to be examined, the second is an accumulator and the third is the final count (which won't be unified until the very end). There are two possible cases.

If the tree is empty, we have the final count:
```
count_even( btree , N , N ) .
```

If the tree is non-empty, we examine the current node, then recursively walk the left and right child trees, thusly:

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  )
  .

We also need a trivial helper to tell us whether a particular value is even or odd:

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

It should be noted that the data structure you're using is not a b-tree, per se: it is a binary tree.

B-trees are something of a generalization of a height-balanced binary tree optimized for disk storage. Each node has a variable number of keys and a variable number of children (corresponding to the number of keys). For more information, see

Here's a picture of a B-tree:

B-Tree Visualization

And a picture of a binary tree:

Binary Tree Visualization

回复收藏 0 原文

可可 2024-12-31 02:33:54

您必须检查每个节点，看看它是偶数还是奇数，并且只计算偶数。
对你的程序进行简单的修改就可以了（但是我会做一些不同的事情）：

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。

You have to check every node to see if it's even or odd and only count the ones that are even.
A simple modification to your program should do (however I'd do it a bit different):

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.

I just count 1 - Number mod 2 which is 1 when the number is even and 0 otherwise.

回复收藏 0 原文

~没有更多了~