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