Prolog最后一个元素函数返回整个列表。
Prolog最后一个元素函数返回整个列表。
提问于 2021-10-13 17:41:53
我有一个任务要在Prolog中实现快速排序，然后返回最后一个元素。我已经使用了快速排序，但是当它到达最后一个元素调用时，它会返回整个列表。我的最后一个元素在单独运行时工作，但在快速排序结束时调用它就不行了。对于我需要改变什么有什么想法吗？
quicksort([],[]).
quicksort([H|T],Final) :-
partition(T,H,Left,Right),
quicksort(Left,Ls),
quicksort(Right,Rs),
append(Ls,[H|Rs],Sorted),
lastelement(Final, [Sorted]).
partition([],Pivot,[],[]).
partition([H|T],Pivot,[H|Ls],Rs) :- H =< Pivot, partition(T,Pivot,Ls,Rs).
partition([H|T],Pivot,Ls,[H|Rs]) :- H > Pivot, partition(T,Pivot,Ls,Rs).
append([],Sorted,Sorted).
append([H|T],Sorted,[H|Z]) :- append(T,Sorted,Z).
lastelement(Final, [Final]).
lastelement(Final, [_|T]):- lastelement(Final,T).回答 2
Stack Overflow用户
回答已采纳
发布于 2021-10-13 19:28:00
正如@gusbro所观察到的，不可能定义一个递归谓词，其大小写生成一个列表，其递归步骤生成一个元素。因此，一个可能的解决办法是：
quicksort([],[]).
quicksort([H|T], Sorted) :-
mypartition(T, H, Left, Right),
quicksort(Left, Ls),
quicksort(Right, Rs),
myappend(Ls, [H|Rs], Sorted).
mypartition([], _Pivot,[],[]).
mypartition([H|T],Pivot,[H|Ls],Rs) :- H =< Pivot, mypartition(T,Pivot,Ls,Rs).
mypartition([H|T],Pivot,Ls,[H|Rs]) :- H > Pivot, mypartition(T,Pivot,Ls,Rs).
myappend([], Sorted, Sorted).
myappend([H|T], Sorted, [H|Z]) :- myappend(T, Sorted, Z).
lastelement(Final, [Final]).
lastelement(Final, [_|T]):- lastelement(Final,T).
quicksort_last(List, Last) :-
quicksort(List, Sorted),
lastelement(Last, Sorted).示例：
?- quicksort([61,46,59,27,12,38], S).
S = [12, 27, 38, 46, 59, 61] ;
false.
?- quicksort_last([61,46,59,27,12,38], S).
S = 61 ;
false.一个更好的解决方案
quicksort_last/2的平均复杂度为O(n n)。假设您的解决方案必须基于快速排序的思想，一种平均复杂度为O(n)的更有效的方法是：
- 若要有最后一项(也称为最大项)，完整排序列表不能为空。
- 分区之后：
- 如果右子列表为空，则数据透视是完整排序列表中的最后一个元素(因为数据透视比左子列表中的所有元素大)。
- 否则，右侧子列表中的最后一个元素也是完整排序列表中的最后一个元素(因为，如果右边的子列表中至少有一个项，那么数据透视就是比它小)。
quick_last([Pivot|Rest], Last) :-
mypartition(Rest, Pivot, _, Right),
( Right = []
-> Last = Pivot
; quick_last(Right, Last) ).示例：
?- quick_last([61,46,59,27,12,38], S).
S = 61 ;
false.
?- quick_last([71, 100, 83, 97, 62, 6, 42, 3, 40], L).
L = 100 ;
false.在最佳情况下，在quick_last/2的每个递归调用中，列表的长度除以2。由于partition/4消耗的时间与列表的长度成正比，所以T(n) =n+ n/2 + n/4 +…+1≈2*n。
备注这个解是算法在无序列表中找到k个最小元素的一个特殊情况(参见：快速选择)。
Stack Overflow用户
发布于 2021-10-13 19:49:43
lastElement/2似乎试图从排序的list...and中找到最后一个元素，并将其作为列表本身在各种递归调用中传回。例如，调用quicksort(Left,Ls)就好像Ls将是Left的排序版本，但它实际上返回了列表的最后一个元素。
如果您想要最后一个元素，当然，您可以这样做，但是您可以在完成快速排序之后得到它。(或者，可以肯定地说，是以其他方式找到的。)
quicksort([H|T],Sorted) :- partition(T,H,Left,Right),
quicksort(Left,Ls),
quicksort(Right,Rs),
append(Ls,[H|Rs],Sorted).
findLastElement(List,Final) :- quicksort(List,Sorted), lastelement(Final, Sorted).页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69560017
复制相关文章
相似问题
腾讯云开发者
