Prologでbツリー内のすべての偶数を数えよう

Question

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

ありがとうございます。

Answer 1

ビジュアルプロローグについて知らんの何が、通常のプロローグで、私は以下のような何かをしたい...

まず、私は原子btreeとして空のBTREEを意味し、非空のbtreeを表していると思います従ってアリティ3の構造として：PayloadはLeftChildrenとRightChildrenは、それぞれ、現在のノードの左と右の子を表すのbtreeされた状態で、（整数明らかに）ノードのためのデータである

btree(Payload, LeftChildren, RightChildren) 

。

ノードを偶数ノードでカウントするツリーを横断するのは簡単です。パブリック述語は、検査されるべき[bound] btree構造を受け入れるアリティ2と、偶数項目の数を表すバインドされた値またはアンバウンドされた値とを有する。これは、ツリーを歩き、カウントを展開する、内部の再帰的な "ヘルパー"述部を呼び出します。

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

内部述語も同様に単純です。アリティ3を持つと、最初の引数は検査されるツリーであり、2番目はアキュムレータであり、3番目は最後のカウントです（最後まで統一されません）。可能性のあるケースが2つあります。

1. ツリーが空の場合、我々は最終カウントがあります木が空でない場合、我々は現在のノードを調べる

   count_even(btree , N , N) . 
   

2. を、再帰的に左と右の子の木を歩きます、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 ) 
       . 
   

我々はまた、特定の値が偶数か奇数か、私たちに伝えるために些細なヘルパーを必要とする：

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

あなたが使用しているデータ構造はBツリー、自体ではないことに留意すべきである：それはバイナリツリーです。

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. 

私はちょうど数が偶数と0それ以外のとき1である1 - Number mod 2を数えます。