如何在Prolog中找到长度不大于列表长度的三分之一且元素之和最大的列表的子列表?
由于这里没有足够的问题可以回答,因此这里有一些解决此类Prolog问题的一般建议。
您可以使用带有未绑定列表参数的length/2
创建指定长度的列表,例如:
?- length(X, 3).
X = [_3192, _3198, _3204].
当试图回答涉及列表的问题时,这通常很有用。您可以获取列表的长度,然后再次使用length/2
来构建结果列表。
select/3
也是回答这类问题的一个有用谓词,因为它可以用来从列表中挑选项目。例如,如果我想从列表中选择两个项目,我可以这样做:
picktwo(L, [X,Y]) :- select(X, L, L0), select(Y, L0, _).
在这里,我只想返回这两个项目,忽略列表的其余部分,它将在我现在拥有_
的位置上可用。
?- picktwo([7,18,3,4,19], X).
X = [7, 18] ;
X = [7, 3] ;
X = [7, 4] ;
X = [7, 19] ;
X = [18, 7] ;
X = [18, 3] ;
X = [18, 4] ;
X = [18, 19] ;
X = [3, 7] ;
X = [3, 18] ;
X = [3, 4] ;
X = [3, 19] ;
X = [4, 7] ;
X = [4, 18] .
(像我这样的DCG粉丝可能会被这个替代实现逗乐:phrase((select(X), select(Y)), [7,18,3,4,19], _).
)
有一个内置的求和列表,称为sumlist/2
。
通过要求Prolog找到一个比所有其他解决方案都大的解决方案,通常可以以一种相当但效率很低的方式来最大限度地解决问题。这样的代码通常看起来是这样的:
solve(Solution) :-
find_solution(Solution),
+ (find_solution(Solution2), Solution2 > Solution1).
在这里,您是在声明解决方案是最好的,因为没有其他解决方案是更好的。Prolog当然必须进行组合才能找到最佳解决方案,所以这肯定会将O(N log N)搜索变成O(N^2)搜索,但它对小数据集来说还可以。下面是一个查找最大值对的示例:
sumpairs(List, X, Y, Sum) :-
select(X, List, L0), select(Y, L0, _), Sum is X + Y.
largest(List, X, Y) :-
sumpairs(List, X, Y, Sum),
+ (sumpairs(List, _, _, ABSum), ABSum > Sum).
这产生:
?- largest([7,18,3,4,19], X, Y).
X = 18,
Y = 19 ;
X = 19,
Y = 18 ;
false.
所以你可以看到,它的效率非常低,实际上通过排列两次都找到了相同的答案,但如果你在乎的话,你可能会想出一些方法来防止这种情况发生。
这盒零件可能足以让你自己找到问题的答案,祝你好运!