2

私はいくつかのコードを持っています

tree1(tree(1,
            tree(2,
                tree(3,nil,nil),
                tree(4,nil,nil)),
            tree(5,
                tree(6,nil,nil),
                tree(7,nil,nil))
        )
    ).
rbt_count_nodes(e,0):-!.
rbt_count_nodes(t(_,L,R),N):-
    rbt_count_nodes(L,NL),
    rbt_count_nodes(R,NR),
    N=NL+NR+1.

?-tree1(T),rbt_count_nodes(T,N),write(N).

しかし、ゴールは常に No を返します。

4

2 に答える 2

5 
rbt_count_nodes(t(_,L,R),N)

になる必要があります

rbt_count_nodes(tree(_,L,R),N)

と

N=NL+NR+1

になる必要があります

N is NL + NR + 1

（(=)/2統合(is)/2を実行するため、算術を実行するために使用されます）。

と

rbt_count_nodes(e,0):-!.

になる必要があります

rbt_count_nodes(nil,0).

これらの3つの編集の後は問題ないはずですが、テストできないため、間違っていることが判明する可能性があります。

于 2012-05-24T12:18:35.543 に答える
4

別の回答で与えられたメモ ( t->tree および e->empty という用語の名前のis/2代わりに=/2およびタイプミスを使用) に加えて、アキュムレータを使用して、プロローグ システムが末尾再帰を実行できるようにすることを検討する必要があります。

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

rbt_count_nodes(nil,N, N):-!.
rbt_count_nodes(tree(_,L,R),C,N):-
    succ(C, C1),
    rbt_count_nodes(L,C1,NL),
    rbt_count_nodes(R,NL,N).

プロシージャは、2 番目の引数 (アキュムレータ) としてゼロを指定してrbt_count_nodes/2呼び出すだけです。rbt_count_nodes/3各再帰ステップで、このアキュムレータは 1 ずつインクリメントされ、再帰を実行します。ベースケースは、アキュムレータを出力と統合するだけで、システムが末尾再帰を実行してスタックスペースを節約できるようにします。

[編集]

コメントによると、真に末尾再帰にする (つまり、すべての再帰呼び出しを末尾呼び出しにする) には、新しい節を rbt_count_nodes/3 に追加 (および別の節を変更) できます。

rbt_count_nodes(nil,N, N):-!.
rbt_count_nodes(tree(Node,tree(LNode, LL, LR),R),C,N):-
  rbt_count_nodes(tree(Node, LL, tree(LNode, LR, R)), C, N).
rbt_count_nodes(tree(_,nil,R),C,N):-
  succ(C, C1),
  rbt_count_nodes(R,C1, N).

このアプローチでは、最初の節は空のノードを処理し、2 番目の節は現在のノードの右側に分岐を「移動」するツリーの左側を処理し、3 番目の節は単にノードの数を計算します。ノード。

于 2012-05-24T14:49:37.217 に答える