0

b ツリーに存在するすべての偶数のリストを作成するプログラムを Prolog で作成したいと考えています。ここまで書いてきました。ツリー内のすべての要素を数える述語。どこを掻いていいのかわからない。

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

どうもありがとう。

4

2 に答える 2

1

Visual Prologについては何も知りませんが、通常のPrologでは、次のようなことをします...

まず、空の btree をアトムとして示し、空でない btreebtreeをアリティ 3 の構造体として表します。

btree( Payload, LeftChildren, RightChildren )

ここPayloadで、 はノードのデータ (明らかに整数) であり、LeftChildrenとRightChildrenはそれぞれ現在のノードの左と右の子を表す btree です。

ツリーをたどって偶数のノードを持つノードをカウントするのは簡単です。public 述語はアリティ 2 を持ち、検査対象の [bound] btree 構造と、偶数項目の数を表すバインド値または非バインド値を受け入れます。ツリーをたどってカウントを展開する内部の再帰的な「ヘルパー」述語を呼び出します。

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

内部述語も単純です。アリティが 3 の場合、最初の引数は調べるツリー、2 番目はアキュムレータ、3 番目は最終カウント (最後まで統一されません) です。考えられるケースは 2 つあります。

  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 ツリーではないことに注意してください。これはバイナリ ツリーです。

B ツリーは、ディスク ストレージ用に最適化された、高さのバランスが取れたバイナリ ツリーを一般化したものです。各ノードには、可変数のキーと可変数の子 (キーの数に対応) があります。詳細については、次を参照してください。

B ツリーの図を次に示します。

B ツリーの視覚化

二分木の写真:

二分木の視覚化

于 2012-01-04T18:17:29.263 に答える
0

すべてのノードをチェックして偶数か奇数かを確認し、偶数のノードのみをカウントする必要があります。プログラムを簡単に変更するだけで済みます (ただし、私は少し違う方法で行います)。

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 になるようにカウントします。

于 2012-01-04T13:28:31.223 に答える