gpt4 book ai didi

recursion - Prolog 递归返回多个结果

转载 作者:行者123 更新时间:2023-12-03 22:21:27 25 4
gpt4 key购买 nike

首先,这是一个摆在我面前的作业问题。

我应该写一个谓词 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) 并为其提供 BT 时,如果深度为 4,则它会递归 4 次并“返回”数字 4 四次。根据我的教授的说法,这是一种不正确的行为,因为它应该只返回数字 4 一次。 (使用上面的例子,它返回数字 2 两次)

这是我第一次在 Prolog 中编码,我不知道应该从哪里开始寻找。

如果它有所作为,这在技术上是 SWI-Prolog...

最佳答案

由于这是作业,我不会给你完整的解决方案。

当您的谓词遇到匹配 node(leaf, _, leaf) 的节点时,它首先执行第二个子句。那返回一个。然后,当你要求它回溯时,它也会执行第三个子句,因为它也匹配了 LT=leaf 的输入。和 RT=leaf ,所以它会递归两次并命中 leaf两种情况。

下次遇到这种问题要自己调试,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。)

关于recursion - Prolog 递归返回多个结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12868485/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com