我在 prolog 中實作代碼時遇到了一些問題，因為我發現它有點難以理解，因為我習慣于正常編碼:(
我必須對整數串列進行排序，但它必須保留重復的值。我試圖想出一個解決方案，我會使用冒泡排序，但我不知道如何在序言中撰寫它......如果有人可以逐步解釋代碼并啟發我，我將非常感激......
是的，我遇到的另一個問題是對由整數和數字串列組成的串列進行排序......我不知道如何從這個開始......例如：[1,2,[4,1,4] , 3, 6, [7, 10, 1, 3, 9], 5, [1, 1, 1], 7] 需要輸出 [1, 2, [1, 4, 4], 3, 6, [ 1、3、7、9、10]、5、[1、1、1]、7]。
我試圖撰寫一些代碼，但它根本不起作用，我放棄了......我從互聯網上復制了一些東西來解決第一個問題，但這對我來說真的沒有意義......
uj5u.com熱心網友回復：
Prolog是正常的編碼??
它只是不是命令式編碼，它本質上是遞回的。您需要停止以命令式的方式思考（告訴計算要做什么），并且需要開始遞回思考（關于該主題的好書。）
MergeSort是您的朋友。它是一種穩定的遞回排序演算法，性能好，非常適合 prolog 的作業方式。它的作業方式很簡單：
- 根據定義，空串列是有序的。
- 根據定義，長度為 1 的串列也是有序的。
- 對于長度 > 1 的串列，
- 將串列分成兩半，
- 遞回地對每一個進行排序，并且
- 將兩個現在排序的串列合并在一起。
這里的所有都是它的。
所以，我們需要三樣東西：
- 將串列分成兩半的謂詞，
- 將兩個有序串列合并為一個有序串列的謂詞，以及
- 使用這 2 個助手對串列進行排序的謂詞。
劃分
對串列進行磁區很容易。有兩種終止遞回的特殊情況和一種一般情況。特殊情況是微不足道的：
- 空串列 (
[]) 被劃分為 2 個空串列partition( [] , [] , [] ) . - 長度為 1 的串列被劃分為自身和一個空串列：
partition( [L] , [L] , [] ) .
一般情況下，長度大于 1 的串列幾乎不會更復雜。在這里，我們只取串列中的前兩項，將一項分配給左側磁區，另一項分配給右側磁區，然后我們向下遞回處理剩余部分：
partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs).
把它們放在一起，你得到partition/3：
partition( [] , [] , [] ) .
partition( [L] , [L] , [] ) .
partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs) .
合并
Merging 2 ordered lists into one ordered list is likewise simple. We have 3 special cases that terminate recursion, and one general case. The special cases are those where one source list is empty and the other is not, and the case of both source lists being the empty list:
merge( [] , [] , [] ) .
merge( [L|Ls] , [] , [L|Ls] ) .
merge( [] , [R|Rs] , [R|Rs] ) .
The general, recursive case, where the two source lists are non-empty is a little tricker (but not much). You have
- the case where the left head collates before or equal to the right head, and
- the case where the left head collates after the right head.
We can use Prolog's in-built operators for the comparison of terms to determine collation sequence:
merge( [L|Ls] , [R|Rs] , [L|Xs] ) :- L @=< R, merge( Ls , [R|Rs] , Xs ) .
merge( [L|Ls] , [R|Rs] , [R|Xs] ) :- L @> R, merge( [L|Ls] , Rs , Xs ) .
Putting it all together, you get merge/3:
merge( [] , [] , [] ) .
merge( [L|Ls] , [] , [L|Ls] ) .
merge( [] , [R|Rs] , [R|Rs] ) .
merge( [L|Ls] , [R|Rs] , [L|Xs] ) :- L @=< R, merge( Ls , [R|Rs] , Xs ) .
merge( [L|Ls] , [R|Rs] , [R|Xs] ) :- L @> R, merge( [L|Ls] , Rs , Xs ) .
Sort
And sorting is likewise easy. There are 2 special cases that terminate execution, the empty list and a list of length 1, both of which are ordered by definition. The general recursive case, for lists of length greater than 1 is
- partition the list,
- recursively sort each half, and
- merge the two now-sorted lists
Thus:
merge_sort( [] , [] ) .
merge_sort( [X] , [X] ) .
merge_sort( [X,Y|Zs] , Ys ) :-
partition( [X,Y|Zs], L0, R0 ) ,
merge_sort(L0,Ls),
merge_sort(R0,Rs),
merge(Ls,Rs,Ys)
.
Whole Enchilada
You can fiddle with this at https://swish.swi-prolog.org/p/SCBlSONF.pl
partition( [] , [] , [] ) .
partition( [L] , [L] , [] ) .
partition( [L,R|Xs] , [L|Ls] , [R|Rs] ) :- partition(Xs,Ls,Rs) .
merge( [] , [] , [] ) .
merge( [L|Ls] , [] , [L|Ls] ) .
merge( [] , [R|Rs] , [R|Rs] ) .
merge( [L|Ls] , [R|Rs] , [L|Xs] ) :- L @=< R, merge( Ls , [R|Rs] , Xs ) .
merge( [L|Ls] , [R|Rs] , [R|Xs] ) :- L @> R, merge( [L|Ls] , Rs , Xs ) .
merge_sort( [] , [] ) .
merge_sort( [X] , [X] ) .
merge_sort( [X,Y|Zs] , Ys ) :-
partition( [X,Y|Zs], L0, R0 ) ,
merge_sort(L0,Ls),
merge_sort(R0,Rs),
merge(Ls,Rs,Ys)
.
You might notice that most of the work in this program consists of pattern matching in the heads of each predicate's clauses. That's a big part of what makes Prolog as expressive and concise as it is.
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/454053.html