我有以下用于快速排序的序言代码:
gt(X,Y):- X @> Y.
conc([], List, List).
conc([Head|Tail], List1, [Head|List2]):- conc(Tail, List1, List2).
quicksort([], []).
quicksort([X|Tail], Sorted):-
split(X,Tail,Small,Big),
quicksort(Small,SortedSmall),
quicksort(Big, SortedBig),
conc(SortedSmall, [X|SortedBig], Sorted).
split(X,[],[],[]).
split(X,[Y|Tail],[Y|Small],Big):-
gt(X,Y),
!,
split(X,Tail,Small, Big).
split(X,[Y|Tail],Small,[Y|Big]):-
split(X,Tail,Small,Big).
例如数组是[3,2,4,1,5]。快速排序([3,2,4,1,5],已排序)。我需要了解程序的运行轨迹。我几乎做到了,但有一点我没有:(这只是跟踪的一部分):
Redo: (11) split(3, [5], _G3785, _G3782) ? creep
Call: (12) split(3, [], _G3785, _G3788) ? creep
Exit: (12) split(3, [], [], []) ? creep
Exit: (11) split(3, [5], [], [5]) ? creep
Exit: (10) split(3, [1, 5], [1], [5]) ? creep
Exit: (9) split(3, [4, 1, 5], [1], [4, 5]) ? creep
Exit: (8) split(3, [2, 4, 1, 5], [2, 1], [4, 5]) ? creep
为什么我们有 Exit: (11) split(3, [5], [], [5]) ?爬到第 11 行,5 从哪里来? 有人可以帮助我吗?我真的很感激。
最佳答案
我们将以此作为引用:
[1] split(X,[],[],[]).
[2] split(X,[Y|Tail],[Y|Small],Big):-
gt(X,Y),
split(X,Tail,Small, Big).
[3] split(X,[Y|Tail],Small,[Y|Big]):-
split(X,Tail,Small,Big).
我们将跟踪您的跟踪片段。
Redo: (11) split(3, [5], _G3785, _G3782) ? creep
此重做是由于自 gt(3,5)
以来原始查询中的子句 [2] 失败(未显示,在跟踪之前)是假的。然后重做将导致子句 [3] 的查询。我们将替换已知的实例化变量,看看第三个子句查询是什么样子的:
[A] split(3, [5|[]], Small, [5|Big]) :- split(3, [], Small, Big)
这将导致下一个跟踪行,其中 _G3785
是 Small
,和_G3788
是 Big
:
Call: (12) split(3, [], _G3785, _G3788) ? creep
这将在第一个子句 [1] 上成功并产生跟踪的这一部分:
Exit: (12) split(3, [], [], []) ? creep
由于这是在执行上面的子句 [3] 期间(如 [A] 所示),因此从现在起它会产生以下结果 Small
已实例化为 []
和Big
与 []
.
split(3, [5|[]], [], [5|[]])
换句话说,执行[A]中显示的第三个子句会导致:
split(3, [5], [], [5])
下一条跟踪线显示的是:
Exit: (11) split(3, [5], [], [5]) ? creep
关于sorting - 理解prolog中快速排序的运行轨迹,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26648556/