看板 Grad-ProbAsk 關於我們 聯絡資訊
倒數第二題 女男配對問題 四女 五男 女1不配男1,3,5 女2不配男1,4 女3不配男2,4,5 女4不配男4 問可能的配對方法數 詳細的配對限制忘記了 不過大概就是要問這種問題 請問怎樣做呢 排容 ? 暴力法畫tree ? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.126.125.176
losew:排容原理...吧 03/08 14:50
gorocky:我也想知道... 03/08 14:52
leeheng:因為前兩個女生的條件不衝突,所以我想說3*2在去乘下面的 03/08 14:55
EntHeEnd:排容的交集 似乎不好討論...? 03/08 14:55
leeheng:不過排一排就變成暴力解了-.-,答案寫18。 03/08 14:56
gorocky:我也寫18---brute 03/08 15:01
EntHeEnd:hmm... 03/08 15:01
stevenwin:聽說是用rook polynamial 03/08 15:13
losew:題目可能記錯了喔 算出來取兩兩交集方法數大於所有? 03/08 15:19
losew:不過我記得女1是配男1 3 5沒錯 03/08 15:19
fef92:女2 2,3才對 女3忘了 03/08 15:20
fef92: 2,4 03/08 15:20
EntHeEnd:的確忘記原本數據了... 03/08 15:23
EntHeEnd:好像真的要用rook polynomial耶 現在正在看 orz... 03/08 15:24
losew:@@" 如果用排容原理要怎麼求|U|? 03/08 15:40
losew:本來以為是5相異物排4個...應該不是 03/08 15:41
ggyyalex:聽說樹狀圖討論解集合也可行 可能解少 解出的速度也還OK 03/08 15:45
EntHeEnd:嗯嗯... 就是畫tree解吧... leaf個數即是... 03/08 16:08
qwertz:這題用排容作是18沒錯... 不過兩個交集比較麻煩一些.. 03/08 16:45
qwertz:考試的時候太緊張了.. 第一個5!竟然寫成5^4 實在太扯了.. 03/08 16:46
kshswind:我在抉擇暴力法還是排容 最後用排容寫對了上天有保佑= = 03/08 18:08