Re: [請益] 徵求強者解決程式難題

看板Programming作者yauhh (喲)時間13年前 (2011/12/09 00:19)推噓2(2推 0噓 3→)

留言5則, 3人參與討論串4/4 (看更多)

※ 引述《imorgan (ｉ。摩根)》之銘言： : 需求： : 1. 1~50任意選出25各數字成為一組（代號a$），剩餘25各數字為該組剩餘數（代號b$） : 2. 共需20組a1~a20(與相對應之b1~b20) : 3. 以a來講，總共會產生500各數字(25*20=500) : 4. 以a來講，1~50每各數字出現次數為10次(50*10=500) : 5. 以a來講，碰撞次數限制為4~6 : 碰撞定義：任意兩組號碼，同時出現在一組a中稱為一次。 : 根據此一定義，任意兩各數字 in 20組a中，碰撞次數n範圍：0<=n<=10 : 碰撞舉例： : 有一組a1產出為(1,2,3,4,5,...,25) : (1,2)的碰撞次數為1次，(1,3)(1,4)(1,5)...(24,25)亦同 : 6. 呈現上述20組a與其對應之20組b，共20*25=500各數字(與其對應各組剩餘b)，統計並 : 呈現所有碰撞組合之次數你這個難題,我用Prolog寫了一點點如下: (SWI-Prolog) univ(U) :- numlist(1, 50, U). % universe 就是 1~50 而已 count(_N, 1). % 一句廢話,對任何東西計算一次, 得數目為 1 % 從 List 中挑走 N 個, 得子串列為 Part, 剩餘串列為 Rest. select(0, List, [], List) :- !. select(N, [H|T], [H|Part], Rest) :- N1 is N-1, select(N1, T, Part, Rest), length([H|Part], N). select(N, [H|T], Part, [H|Rest]) :- select(N, T, Part, Rest), length(Part, N). % 將 List 平分, 分配的每份子串列之長度必為 Length. divide(List, Length, [List]) :- length(List, Length), !. divide(List, Length, [Part|Result]) :- select(Length, List, Part, Rest), divide(Rest, Length, Result). 然後使用以下查詢就可以得到左半A組資料: (在測試時寫錯了,只弄出10組,速度快; 改為產生A20則費比較多時間.) univ(U), % 令 U = {1, 2, ..., 50}, repeat_list(U, 10, U10), % 收集10份U的內容, length(U, Lu), Lhf is Lu / 2, divide(U10, Lhf, A20), %將U10分為20組A, bagof(XYs, (member(An, A20), % 確認每個An組包含的項目皆獨一, forall((member(A, An), select(A, An, Am)), not(member(A, Am))), bagof((X,Y), (member(X, An), member(Y, An), X < Y), XYs)), XYss), % 並收集所有的成對號碼, flatten(XYss, XYs1), % 合併為A組全部的成對號碼. map_list_to_pairs(count, XYs1, Ps), % 將每個成對號碼都數一次, transpose_pairs(Ps, Tps), keysort(Tps, Sps), group_pairs_by_key(Sps, Gsps), % 數算的結果整理成 "配對 - 數算次數" 的集合. forall((member(_-Cs, Gsps), length(Cs, Lcs)), (Lcs = 4; Lcs = 5; Lcs = 6)), % 確認每個成對數字的數算次數為 {4, 5, 6} 之一, bagof(Assoc-Lcs, (member(Assoc-Cs, Gsps), length(Cs, Lcs)), Assocs), % 並將每個成對數字的出現次數彙總, ("配對 - 出現次數") transpose_pairs(Assocs, Scossa), keysort(Scossa, SScossa), group_pairs_by_key(SScossa, Gscossa), % 彙總結果還可以翻轉再彙總為 "出現次數 - 各種配對情況" 的對應表. % 印出A組內容, nl, write('Left set:'), nl, write(A20), % 印出每個配對的出現次數, nl, write('Number of associating items:'), nl, write(Assocs), nl, % 最後印出每個出現次數的配對案例數目, 完成. nl, write('Statistics of associtation:'), nl, write(Gscossa), foreach(member(Times-Instances, Gscossa), (length(Instances, Li), nl, write(Times), write(': '), write(Li), write(' occurrence'), nl)). -- /yau -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.67.186