-4

mergealt(X,Y,Z)如果列表 Z 是列表 X 和 Y 中替代元素的合并，我需要编写一个成功的 Prolog 谓词。

输入和输出如下所示：

?- mergealt([1,2,3,4],[6,7,8],Z).
Z = [1, 7, 3] .
?- mergealt([1,2,3,4],[6,7,8,9],Z).
Z = [1, 7, 3, 9] .
?- mergealt([1,2,3,4],[6,7,8,9,10],Z).
Z = [1, 7, 3, 9] .

我真的不明白递归。我怎样才能开始解决这个问题？

4

2 回答 2

5

Prolog 可以被认为是声明性语言的“旗手”。所以试着描述你的问题，自上而下：

mergealt(X, Y, Z) :-
  'take first element from X and put it in Z',
  'discard first element from Y',
  'mergealt rest-of-X and rest-of-Y, but exchange them'.

如果 X 中没有元素，则无法完成第一步。这一事实突出了递归终止的情况。最初，Prolog 没有使用if then else，而是将替代品声明为不同的规则：

mergealt([], _Y, []).

在这里您可以看到，pattern matching在第一个参数中，它是区分备选方案的关键，并且在上下文中，Z 被绑定到一个空列表。Y 是未使用的，所以它被标记为匿名占位符，只是为了避免警告。

那么这个更简单的案例表明我们应该使用模式匹配来完成那些冗长的描述。看看您是否可以按照以下准则完成该过程：

mergealt([X|Xs], Y, [X|Zs]) :-
  % take first element from X and put it in Z : done in the head
  % discard first element from Y : see below
  % mergealt rest-of-X and rest-of-Y, but exchange them'. : make your recursive call

discard_first_element([_|Rest], Rest).
% why is this necessary? do you see where it fails if we don't specify this case?
discard_first_element([], []).
于 2012-05-21T08:54:50.050 回答
2
  • 请注意，结果总是从第一个列表的第一个元素开始。
  • 这意味着，如果第一个列表为空，您马上就知道答案。
  • 还要注意，如果它不为空，我们已经知道结果的第一项，所以我们需要使用 mergealt 来计算其余的。但是“其余”将第二个列表的第二项作为结果的第一项，正如我们上面所说，这意味着调用 mergealt 来计算它必须是第一项列表（是的，这是棘手的部分）。
于 2012-05-21T00:02:23.827 回答