4

まず、これは宿題の質問です。

二分木を取り、（今のところ）木の高さを返す述語btree_height\2を書くことになっています。

二分木は次のように表されます。

node(node(leaf, x, leaf), x, node(leaf, x, leaf))

ここで、xはノードの整数値です。（これは単なるサンプルツリーです）。

私のコードは次のとおりです。

btree_height(leaf, 0).
btree_height(node(leaf,_,leaf), 1).
btree_height(node(LT,_,RT), D):-
    btree_height(LT, DL), 
    btree_height(RT, DR),
    D is max(DL,DR)+1.

私が抱えている問題は、btree_height（BT、D）を呼び出して、深さが4の場合にBTを指定すると、4回繰り返され、数値4が4回「返される」ことです。私の教授によると、これは数字の4を1回だけ返す必要があるため、これは正しくない動作です。（上記の例を使用すると、数値2が2回返されます）

Prologでコーディングするのはこれが初めてで、どこから始めればよいかわかりません。

それが違いを生むならば、これは技術的にはSWI-Prologです...

4

1 に答える 1

2

これは宿題なので、完全な解決策は提供しません。

述語がに一致するノードにヒットするnode(leaf, _, leaf)と、最初に2番目の句が実行されます。それは1つを返します。次に、バックトラックするように要求すると、3番目の句も実行されます。これは入力ととが一致するため、2回繰り返され、両方のケースにヒットします。LT=leafRT=leafleaf

次回、この種の問題を自分でデバッグする必要がある場合trace/1は、優れたツールです。

2 ?- trace.
true.

[trace] 2 ?- btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), H).
   Call: (6) btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), _G821) ? creep
   Call: (7) btree_height(node(leaf, x, leaf), _G903) ? creep
   Exit: (7) btree_height(node(leaf, x, leaf), 1) ? creep
   Call: (7) btree_height(node(leaf, x, leaf), _G903) ? creep
   Exit: (7) btree_height(node(leaf, x, leaf), 1) ? creep
   Call: (7) _G821 is max(1, 1)+1 ? creep
   Exit: (7) 2 is max(1, 1)+1 ? creep
   Exit: (6) btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), 2) ? creep
H = 2 ;
   Redo: (7) btree_height(node(leaf, x, leaf), _G903) ? creep
   Call: (8) btree_height(leaf, _G903) ? creep
   Exit: (8) btree_height(leaf, 0) ? creep
   Call: (8) btree_height(leaf, _G903) ? creep
   Exit: (8) btree_height(leaf, 0) ? creep
   Call: (8) _G911 is max(0, 0)+1 ? creep
   Exit: (8) 1 is max(0, 0)+1 ? creep
   Exit: (7) btree_height(node(leaf, x, leaf), 1) ? creep
   Call: (7) _G821 is max(1, 1)+1 ? creep
   Exit: (7) 2 is max(1, 1)+1 ? creep
   Exit: (6) btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), 2) ? creep
H = 2

（それが言うところcreep、私は押しEnterました。）

于 2012-10-12T23:52:33.510 に答える