※ 引述《korea01 (包仔)》之銘言： : 最近要寫prolog程式(about max heap) : 但~對prolog語言不熟悉 : 連最基本該如何下手都不知道~ : 不曉得有誰能救救我一下>"< : 好困擾唷~上網找都找不到詳細一點的~ : 完全沒頭緒 : 我只會寫C&C++程式&一點點JAVA~ : 請會的人教教我&指導我吧!! : 謝謝^^ 要先知道什麼叫 max heap. 先瀏覽過資料結構方面的文件或書籍. Max heap 的特性大概是說: 1) 是tree 2) 每個節點的key值都不大於父節點的key值. 然後可用程式寫出這個結構: 1. 建立樹: 怎樣建立樹? 先把樹定義為二種情況, nil 或 t(K,L,R), K一定要是數字. 而 L 和 R 也是樹,也就是說,二個也都分別可能是 nil 或t(K,L',R'). 然後可以寫一個predicate建樹. 建立一棵樹要有輸入項,我們說用一列數字丟下去,讓數字變成一棵樹, tree([], nil). tree([N|Rest], t(N,L,R)) :- partition(Rest, Nums1, Nums2), tree(Nums1, L), tree(Nums2, R). 第一句說,沒資料就出現一棵 nil 樹. 第二句說,拿到一列數字,可以先把第一個數字放在樹根,然後要想辦法產生子樹. 假設有另一個predicate稱為partition,給它一列數字,它可以把這列數字分開成兩部份, 於是,你要用它把 Rest 分成 Nums1 和 Nums2, 然後 Nums1 可以建左子樹, Nums2 可建右子樹. 藉由 Prolog 的執行時的 backtracking, partition/3 會幫你產生 各式各樣可能的分配方式. 而接下來,問題就在於 partition/3 該怎麼定義才好. 這裡是一個提示,其他部份你可以自己想清楚. 2. 建立 max heap 樹: 前面提到只是按輸入一列數字的順序產生樹. 第一個數字一定是樹根. 回想 max heap 的特性,說,每個節點key值都不大於樹根key值,換句話說, 樹根key值大於或等於其他每一個節點. 所以,考量前面建立樹的方式,只要把輸入的數字列調整成每一列的第一個數字 一定不小於後面其他數字. 對前面的 tree/2 來說,還要去改 partition/3 是一些麻煩事; 或者說, 你思考 partition/3 的內容還要同時顧到第一數字要不小於後面數字,比較花費精神. 這時候可以使用「產生→檢查」的程式風格,先隨意產生大量並包含全部解答的集合, 之後再使用一些檢查將合理的項目挑出來. 如果我收到一列數字,只要檢查第一個數字不小於後面其他數字,程式這樣做: notlessthan([]). notlessthan([N]). notlessthan([N1,N2|Rest]) :- N1 >= N2, notlessthan([N1|Rest]). 然後看看前面tree/2第二句,用到 partition/3 之後得到的 Nums1 和 Nums2 需要檢查. 於是,把 tree/2 第二句改成: tree([N|Rest], t(N,L,R)) :- partition(Rest, Nums1, Nums2), notlessthan(Nums1), notlessthan(Nums2), tree(Nums1, L), tree(Nums2, R). 另一方面,執行程式時,呼叫 tree/2 所給的那一列數字, > tree([10,1,2,3,4,5,6,7,8,9], T). ... blah blah blah ... 也要確定第一個數字不小於後續數字. 這看要多寫一點程式處理,或是用手工處理,你可以自己決定. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.160.211.92