我有關於快速排序此快速排序here .The序言代碼前面的問題:跟蹤路由 - 序言
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).
[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).
例如該陣列爲[3,2,4,1,5] 。這是跟蹤路由的第一部分:
?- trace, quicksort([3,2,4,1,5], Sorted).
1 Call: (7) quicksort([3, 2, 4, 1, 5], _G4136) ? creep
2 Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270) ? creep
3 Call: (9) gt(3, 2) ? creep
4 Call: (10) [email protected]>2 ? creep
5 Exit: (10) [email protected]>2 ? creep
6 Exit: (9) gt(3, 2) ? creep
7 Call: (9) split(3, [4, 1, 5], _G4261, _G4273) ? creep
8 Call: (10) gt(3, 4) ? creep
9 Call: (11) [email protected]>4 ? creep
10 Fail: (11) [email protected]>4 ? creep
11 Fail: (10) gt(3, 4) ? creep
12 Redo: (9) split(3, [4, 1, 5], _G4261, _G4273) ? creep
13 Call: (10) split(3, [1, 5], _G4261, _G4264) ? creep
在2號線,序言申請拆分的規則[2],我們有Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270)
,我們有_G4269
是[2|Small]
和_G4270
是Big
。
然後比較3和2,gt(3,2)
返回true,它不執行切割。繼續使用split(X,Tail,Small,Big)
即Call: (9) split(3, [4, 1, 5], _G4261, _G4273)
如果gt(X,Y)
返回false,prolog將執行剪切,然後應用分割的規則[3](第11-12行)。
我做對了,爲什麼最後一個變量變成了新變量(_G4237
而不是_G4270
)?因爲在代碼中我認爲它是一樣的。
任何人都可以幫我清楚一些事情嗎? 非常感謝!
每個對predicat的調用都有自己的變量。你的蹤跡顯示深度爲(8)的'_G4270'和深度爲(9)的'_G4273'。所以他們是不同的。 – lurker 2014-10-31 16:59:38
您可以信任變量名稱,特別是何時由算法生成! – CapelliC 2014-10-31 23:58:56