时间戳

首页 > 解决方案 > Prolog最后一个元素函数返回整个列表

prolog - Prolog最后一个元素函数返回整个列表

问题描述

我有一个任务是在 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).

标签： prolog

解决方案

正如@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 lg n)。假设您的解决方案必须基于快速排序的想法，一种更有效的方法，平均复杂时间为 O(n)，是：

  • 要拥有最后一项（也就是最大项），完整的排序列表不能为空。
  • 分区后：
    • 如果右子列表为空，则 Pivot 是完整排序列表中的最后一个元素（因为 Pivot大于左子列表中的所有元素）。
    • 否则，右子列表中的最后一个元素也是完整排序列表中的最后一个元素（因为，如果右子列表中至少有一项，则 Pivot小于它）。
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个最小元素的算法的特例（请参阅：快速选择）。

推荐阅读