2

私はプロローグを学ぼうとしていて、おもちゃの例の1つに行き詰まりました。binary_treeと定義されている：

「-」(マイナス記号) という用語は、空のツリーを表します。項 t(L,V,R) は、左部分木 L、ノード値 V、および右部分木 R を持つツリーを表します。

size(Tree,N)今、ツリーのサイズを見つけるための述語を書き込もうとしています。次を使用して可能であることを知っています：

size( -,0).
size( t(L, _,R), S) :- size(L,Ls), size(R,Rs), S is Ls + Rs + 1.

しかし、アキュムレータを使用して機能させたいと考えています。私は（そして他のいくつかのもの）のようなものに疲れましたが、どれも機能していません：

size(t(L,_,R),N):-size(t(L,_,R),0,N).

size(-,A,A).
size(t(L,_,R),A,N):- A1 is A+1,size(L,A1,N1),size(R,A1,N2), N is N1+N2.

たとえば、テストケースの場合：

size(t(-,n,t(-,m,-)),N).

5の代わりに取得し2ます。ここにトレースがあります：

[debug] [7] 85 ?- trace,size(t(-,n,t(-,m,-)),N).
   Call: (73) size(t(-, n, t(-, m, -)), _G10307) ? creep
   Call: (74) size(t(-, _G10422, t(-, m, -)), 0, _G10307) ? creep
   Call: (75) _G10435 is 0+1 ? creep
   Exit: (75) 1 is 0+1 ? creep
   Call: (75) size(-, 1, _G10437) ? creep
   Exit: (75) size(-, 1, 1) ? creep
   Call: (75) size(t(-, m, -), 1, _G10437) ? creep
   Call: (76) _G10438 is 1+1 ? creep
   Exit: (76) 2 is 1+1 ? creep
   Call: (76) size(-, 2, _G10440) ? creep
   Exit: (76) size(-, 2, 2) ? creep
   Call: (76) size(-, 2, _G10440) ? creep
   Exit: (76) size(-, 2, 2) ? creep
   Call: (76) _G10441 is 2+2 ? creep
   Exit: (76) 4 is 2+2 ? creep
   Exit: (75) size(t(-, m, -), 1, 4) ? creep
   Call: (75) _G10307 is 1+4 ? creep
   Exit: (75) 5 is 1+4 ? creep
   Exit: (74) size(t(-, _G10422, t(-, m, -)), 0, 5) ? creep
   Exit: (73) size(t(-, n, t(-, m, -)), 5) ? creep
N = 5.

2つの異なるアキュムレータが必要だと感じていますが、その方法がわかりません。このことを学ぼうとしているので、（直接的な答えではなく）説明をいただければ幸いです。

4

1 に答える 1

3

サブツリーを 2 回カウントしています:

size(t(L,_,R),A,N):- A1 is A+1,size(L,A1,N1),size(R,A1,N2), N is N1+N2.
                                      ^^            ^^      ^^^^^^^^

値A1は 2 回使用されます。実際に必要なのは、違いを説明することです (違いのリストではなく、非常によく似たもの)。

size(-, N,N).            % N-N   ... 0
size(t(L,_,R), N0,N) :-  % N-N0  ... the total size
   N1 is N0+1,           % N1-N0 ... 1
   size(L, N1,N2),       % N2-N1 ... size of L
   size(R, N2,N).        % N-N2  ... size of R

変数のパターンに注意してください。最初はN0で、最後はNです。それらはほとんど靴紐のように広がっています。

于 2014-07-12T17:12:05.607 に答える