Re: [問題] 關於prolog

看板Programming作者yauhh (喲)時間15年前 (2010/05/29 22:45)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《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