Re: [請益] 徵求強者解決程式難題
※ 引述《imorgan (ｉ。摩根)》之銘言：
: 需求：
翻譯:
: 1. 1~50任意選出25各數字成為一組（代號a$），剩餘25各數字為該組剩餘數（代號b$）
把50個數字分為二組,
: 2. 共需20組a1~a20(與相對應之b1~b20)
以二組為一對,總共需要取20對.
: 3. 以a來講，總共會產生500各數字(25*20=500)
(這句可以忽略,因為以上步驟一定產生這個結果.)
: 4. 以a來講，1~50每各數字出現次數為10次(50*10=500)
限制:將20對數列的前項收集起來,1~50的每個數字各在前項集合中出現10次.
: 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)亦同
這段看得挺模糊的. 以a1來看,(1,2)碰撞了1次.
總共有a1,a2,...a20,以其中平均1,2都出現10次來講,
意思是最好有5組找得到(1,2),其他15組要嘛有1沒有2,要嘛有2沒有1,
要嘛(1,2)都沒有,是這樣嗎?
: 6. 呈現上述20組a與其對應之20組b，共20*25=500各數字(與其對應各組剩餘b)，統計並
: 呈現所有碰撞組合之次數
: 目前計算總碰撞次數為C(25:2)*20=6000
: C(25:2)代表從25各號碼當中，任意取出2各號碼的次數
: 20代表共20組，算出來6000代表為這20組共500各號碼各自在每一組的總碰撞組合次數，
: 平均碰撞次數為6000/(50*49/2)=4.89...
在前項集合找到的碰撞次數 + 在後項集合找到的碰撞次數?
這20對數字,你只想要取一份就夠了? 或者是最好能把所有的數列對窮舉出來?
: 願意付15KNTD給寫得出來的人，程式語言不限，但要能成功移植平台給我。
^^^
好好喔~
: 這問題困擾我很久了，一直想個方法解決，可以搜尋我的id一年半之前就有po過類似的，
^^^^^^^^^^^^
看到這覺得有點疑惑,是連演算法都找不出來嗎?
1,2點是隨機取集合 + 求差集.
4.5點是重複將目標集合取出來,然後用一些檢查函數確認,如果不符合就重新
取目標集合,再做檢查.
第6點就是統計,列表. 但第6點就是在第5點進行的時候順便可以做了.
第5點就是把前項集合每一列都拆成數對,丟到數對集合,就很好統計了.
因為取隨機組合是很瘋狂的舉動,要找到符合的集合就是靠運氣,所以要消耗時間.
如果不要消耗時間,那就只好改用推理方式生成符合的目標集合.
不過使用推理就有太強的引導性,可能不符合你所研究事物的目的.
另一個辦法就是考慮先產生前項集合,先把1到50數字複製10倍放在20x25的方陣中,
然後弄亂, 弄亂的限制條件比較簡單,只要檢查每一列數字是否有二個數字重複,
然後檢查碰撞. 等弄亂完了,準備另一個20x25的方陣,將每一列對1~50的補集貼進去,
就可以了.
要不然或者做反向工作,先產生想要的目標數對,例如(1,2)取4個,(1,3)取5個,
(1,4)取6個... 等等,總計(取聯集)1~50數列有10個,然後來打亂產生前項集合.
不過這也要看這種生成方式是否符合你的研究目的.
用一般的程式語言可能很難寫. 這種需要隨便寫一寫讓電腦程式自己產生資料的事,
我個人建議使用Prolog即可.
--
/yau
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.65.211
※ 編輯: yauhh 來自: 61.231.65.211 (12/06 10:14)
→
12/06 23:14, , 1F
12/06 23:14, 1F
令 +:取聯集, -:取差集, *:取交集, =:集合相等, <:左項屬於右集合,
U:{1,2,...,50}, e:{}
令有一目標集合為 T = {a1, a2, ..., a20, b1, b2, ..., b20},
並令a1, a2, ..., a20聯集為A, b1, b2, ..., b20聯集為B,
其中
a1 + b1 = U, a2 + b2 = U, ..., a20 + b20 = U,
且 a1 * b1 = e, a2 * b2 = e, ..., a20 * b20 = e.
且將A分解並收集為數對集合P1, 其中例如 (1,2) < P1,
則 for all (x, y) < P1, (x, y)存在次數 < {4, 5, 6};
同理作用於將B分解並收集的數對集合P2;
且 for all x < U, x在A中出現10次; 同理, for all x < U, x在B中出現10次.
T就是你所說的目標. 或許你說的依照目標做題目是指先取a1, b1, 然後取 a2, b2,
以此類推. 但是假如我先取A,然後取B,你能說這是不照目標嗎?
所以,
→
12/07 00:25, , 2F
12/07 00:25, 2F
※ 編輯: yauhh 來自: 61.231.65.211 (12/07 01:06)
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
