2

我在递归搜索列表和从结果中创建列表列表时遇到问题..

知识库包含团队名称、获胜次数和他们所在的区域，所有这些都与他们的团队编号相关联。我正在传递团队编号列表，Teams并且正在寻找与findMinMax/3. 我需要的结果是...

配对团队列表列表（例如X = [[gonzaga, washington], [iowa, oklahoma], …]）和 1 个不匹配的团队（由奇数个团队产生）或 0（在偶数的情况下）

我想通了其他一切，可以完成部分[gonzaga, washington]，但在递归部分失败......

findPair(Teams,[HL|TL],Rest) :-
    findMinMax(Teams,Min,Max),
    delete(Teams,Min,TeamsNoMin),
    delete(TeamsNoMin,Max,Rest),
    createPair(Min,Max,Pair), %Pair = "["Min_team","Max_team"]"
    append(HL,[Pair],TL),
    findPair(Rest,TL,[]).
4

1 回答 1

6

通用递归方案

在这里，我将尝试向您展示我们通常如何在 Prolog 中执行递归。对于初学者来说，这并不容易，因为列表是“向后”构建的：在我们到达列表末尾之前，什么都不会真正构建。

这种“向后构建”原则的原因是，一旦设置了变量，就不能将其设置为另一个值，因此很难说结果是[1]递归的第一步，然后变成[1, 2]. 相反，我们在 Prolog 中所说的是结果头是1，结果尾是递归调用的结果（是的，如果它变得混乱，请阅读两次：d）。因此，只要我们没有遇到基本情况（不执行递归的情况），我们就不会明确绑定变量（即我们总是让术语的一部分未绑定）。

rec/2: rec(Input, Result)对于通过将其元素与 链接来从输入列表生成结果列表的谓词somepredicate/2，我们将编写：

rec([InputHead|InputTail], [ResultHead|ResultTail]) :-
    somepredicate(InputHead, ResultHead),
    rec(InputTail, ResultTail).

来代表。

在这里你可以看到我们声明结果的头部是ResultHead，并且它的尾部是通过调用计算出来的rec(InputTail, ResultTail).

现在这很好，但我们需要在某个时候停止，例如，当列表为空时。我们会这样写：

rec([], []).

这意味着：当输入列表为空时，结果列表也为空。

对您的谓词的应用

现在，要解决您的问题，您首先必须修复递归子句：

findPair(Teams,[HL|TL],Rest) :-
    findMinMax(Teams,Min,Max),
    delete(Teams,Min,TeamsNoMin),
    delete(TeamsNoMin,Max,Rest),
    createPair(Min,Max,Pair), %Pair = "["Min_team","Max_team"]"
    append(HL,[Pair],TL),
    findPair(Rest,TL,[]).

会成为

findPair(Teams, [Pair|Tail], LeftOver) :-
    findMinMax(Teams, Min, Max),
    delete(Teams, Min, TeamsNoMin),
    delete(TeamsNoMin, Max, Rest),
    createPair(Min, Max, Pair), %Pair = "["Min_team","Max_team"]"
    findPair(Rest, Tail, LeftOver).

需要注意的重要一点：现在Rest已经成为两个独立的变量。的最后一个参数findPair/3不再改变，因为在递归调用中我们还不知道它，所以我们不能绑定它，Rest因此 in-predicate 现在是独立的，只代表没有尚未处理，因此对我们的结果列表的尾部（和LeftOver）感兴趣。

现在我们必须处理基本情况：

  • 当没有队伍时

    findPair([], [], []).

    这里我们说 whenTeams是空的，Resultand 也是LeftOver。

  • 当只剩下一队时

    findPair([Last], [], [Last]).

    这里我们说whenTeams只有一个元素，LeftOver等于Teams且Result为空。

结果代码是：

findPair([], [], []).
findPair([Last], [], [Last]).
findPair(Teams, [Pair|Tail], LeftOver) :-
    findMinMax(Teams, Min, Max),
    delete(Teams, Min, TeamsNoMin),
    delete(TeamsNoMin, Max, Rest),
    createPair(Min, Max, Pair), %Pair = "["Min_team","Max_team"]"
    findPair(Rest, Tail, LeftOver).

要使您的子句排他性，您可以替换Teams为[Not, Empty|AtAll]以确保最后一个子句仅用于长度为 2 或更长的列表，或者仅Teams = [_, _|_],在子句开头添加一个保护。

希望它有所帮助，并毫不犹豫地在评论中要求澄清:)

于 2012-08-20T00:00:11.147 回答