3

我有这个代码用于将输入列表分成两半。好像没问题。

halve(List,A,B) :- halve(List,List,A,B), !.
halve(B,[],[],B).
halve(B,[_],[],B).
halve([H|T],[_,_|T2],[H|A],B) :-halve(T,T2,A,B).

好的，所以我尝试对其进行解码。开头很清楚：

“减半列表和 2 个逻辑变量”是这样的：

halve(List,A,B)

(1) 然后继续这部分：

:- halve(List,List,A,B).

这意味着，我正在从第一个列表中创建新的两个列表（列表、列表）还是什么？什么确切地代表“：-”？我猜新的列表 = 一半将是 A 和 B，对吧？

(2) 其次，拜托，我不太明白这两行：

halve(B,[],[],B).
halve(B,[_],[],B).

也许你可以用一些例子来解释一下，好吗？

(3) 好吧，我希望经过你对（1）和（2）的解释，我会自己得到最后一部分……

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B).

非常感谢你帮助我。

好的，我们的第一个问题已经有了解决方案。长话短说，它的工作原理是这样的：

halve([1,2,3,4,5],[1,2],[3,4,5]). 
->true

如果您注意到它将列表分成两半，但如果列表包含奇数个元素，则后半部分是较大的部分。

现在我想要获得的是让第一个更大。

所以我在想这个：

我要达到这个：

Halves_div([1,2,3],A,B).
A=[1,2],
B=[3].

假设我的输入是列表：[1,2,3]。所以我将从拆分列表的头部和尾部开始：[H|T]然后我将合并H新的空列表 - 我的第一半（A）。之后我有 A=[1]、B=[] 和 Input=[2,3]。

对于合并，我有：

merge([],List,List).
merge([H|T],List,[H|New]) :- merge(T,List,New).

还有一件事-我需要检查第一半是否已经> =第二半，对吗？

所以这是我的想法，我希望你能帮助我的唯一一件事就是把它写在序言中。我有点困惑如何把它放在一起。

谢谢！

看来我的解决方案太复杂了，我找到了更好的东西！

4

3 回答 3

9

首先，Prolog 子句如下所示：

Head :- Body

您可以将其解读为“Head如果Body”或“Body暗示Head”。

请注意，有时您只有

Head

那是因为 Head 总是true。Head在这种情况下，我们宁愿称其为事实，而不是称其为子句。

所以在这里，我们有：

halve(List,A,B) :- halve(List,List,A,B).

这意味着halve(List, A, B)如果为真，halve(List, List, A, B)则为真。具体来说，这只是一种委托 to 工作的halve/3方式halve/4，即所谓的工作者谓词。

为什么我们需要一个工作者谓词？好吧，因为在这里我们想使用另一个变量来计算我们的A和B项。但是我们不能这样做，halve/3因为 3 个参数点halve/3已经被输入列表 、List结果的前半部分和结果的后半部分A占用B。

关于这List, List件事，这只是说我们halve/4使用相同的第一个和第二个参数调用的一种方式，就像在任何编程语言中一样。

然后有趣的事情开始了。Prolog 将尝试证明halve/4对于某些给定参数是正确的。让我们来说明一下我们以halve/3这种方式调用的执行：

?- halve([1, 2], A, B).

然后，如果您遵循我之前所说的内容，Prolog 现在将尝试通过以下参数halve/3证明这是真的：halve/4halve([1, 2], [1, 2], A, B).

为此，Prolog 有 3 个选择。第一个选择是以下子句：

halve(B,[],[],B).

显然，那是行不通的。因为当 Prolog 将尝试通过统一将调用者的第二个参数“放入”被调用者的第二个参数时，它会失败。因为 [1, 2]不能统一[]。

只剩下两个选择，下一个是：

halve(B,[_],[],B).

同样的事情，Prolog 无法统一[1, 2]，[_]因为_它只是一个变量（如果您遇到问题，请参阅我关于匿名变量的帖子）。_

因此，Prolog 必须找到解决您提出的问题的唯一机会是最后一个子句，即：

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B).

在这里，Prolog 会想办法统一事物，让我们看看是哪种方式：

  • 我们必须与[1, 2]统一[H|T]。这意味着H = 1.和T = [2].
  • 我们必须与[1, 2]统一[_,_|T2]。这意味着T2 = [].
  • 现在我们开始使用下一个统一来构建我们的结果，即A = [H|A']（我准备了第二个A，因为变量是局部范围的，它们不一样）。在这里我们告诉我们，当我们从子句的主体计算结果时，我们将添加H到它。在这里H，1我们已经知道Awill 的第一个元素是1。

Ok ok，统一成功，棒棒哒！我们可以进入条款的主体。它只halve/4是以递归方式调用这些值（如上计算）：

halve([2], [], A, B).

在这里，我们重新开始。虽然这次事情会很快，因为 Prolog 的首选将是一个很好的选择：

halve(B,[],[],B).

可以统一为

halve([2], [], A, B).

具有这些值：A = []和B = [2]。

所以这是一个很好的步骤，我们现在达到了递归的“基本情况”。我们现在只需要从下到上构建我们的结果。还记得我们halve/4上面几步递归调用谓词的时候吗？我们已经说过 的第一个元素A是1。现在我们知道尾巴是[]，所以我们可以说A = [1]。我们没有说明任何特别的内容B，因此B = [2]结果保持不变。

既然我详细说明了执行，您可能想知道，为什么会这样？好吧，如果你注意的话，你会注意到第二个参数的halve/4通过速度是第一个参数的两倍。[H|T]与[_, _|T2]。这意味着当我们用第二个参数到达列表末尾时，第一个参数仍然在我们列表的中间。这样我们就可以把事情分成两部分。

我希望我能帮助你抓住这里工作中的一些微妙之处。

于 2012-04-08T15:47:27.360 回答
1

halve(List,A,B)复制Listto的前半部分A并将后半部分与B

当我们的列表长度为偶数时，这将是正确的：halve(B,[],[],B).

当 out 列表的长度为奇数时，这将是正确的：halve(B,[_],[],B).

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B).

在这里，我们设置 2 让我们在每一步中将它们称为“指针”，我们将一个元素从列表的开头复制到，A因为我们想要获得前半部分。
因为在每一步中，我们从列表中删除 2 个元素，[_,_|T2]当列表只有一个左元素或为空时，谓词将停止，然后它将列表的其余部分与B. 如果你看不懂使用trace/0

于 2012-04-08T15:57:19.353 回答
1

这个版本可能证明有用...

split_in_half(Xs, Ys, Zs) :-  length(Xs, Len),
Half is Len // 2,    % // denotes integer division, rounding down
split_at(Xs, Half, Ys, Zs).

split_at(Xs, N, Ys, Zs) :- length(Ys, N), append(Ys, Zs, Xs).
于 2014-01-23T01:30:41.857 回答