作者jameschou (DOG)
看板Math
標題Re: [中學] 三對夫婦排列問題
時間Sun May 8 17:19:33 2011
※ 引述《krauserq (popokaka)》之銘言:
: 在讀排列組合的時候碰到一個問題..怎麼算答案都跟題目給的不一樣
: 所以來板上問一下..
: 題目:有三對夫婦共六人排成一列 每對夫婦均不相鄰的排法有幾種?
: 我的算法是根據排容原理
: 6! -(3x2!x5!) +(3x4!x2!x2!) -(1x3!x2!x2!x2!)
: 全部 一對夫婦相鄰 兩對夫婦相鄰 三對夫婦相鄰
: 兩次算出來答案都是240
: 可是題目給的答案是426種
這題感覺對呀@@
我算也是240
用程式跑答案也是240
可能答案給錯
或者是題目不是這樣@@
: 所以我一直很困惑..
: 想問板上的大大..我的算法有哪裡出了問題嗎 > <
: 順便在補一題
: 甲乙丙丁戊五人排成一列
: 若甲不排第一跟第五的位置
: 乙不排第二跟第三的位置
: 丙不排第三和第四的位置
: 丁不排第五的位置
: 是問共有多少種排法?
: 考完試後老師看了看這一題
: 一開始說用排容解 然後就GG掉了
: 後來他說這一題可以用五階行列式解
: 可是他才寫了兩行就說:開玩笑的辣 這樣解一定解到死..
: 然後就不了了之了..
: 不知道板上有沒有神人大大有除了慢慢討論之外這一題的解法..
第二題我覺得就只能慢慢討論
畢竟題目給的條件也不是什麼有規律的條件
不過戊顯然沒有被任何條件限制住
所以我的想法就是先排好甲乙丙丁 剩下的位置放入戊就好
然後呢...
我還是用暴力法= =...
首先五個位子裡面只看甲乙丙丁的話可以放哪個
一 | 二 | 三 | 四 | 五
------------------------------------------
乙 | 甲 | 甲 | 甲 | 乙
丙 | 丙 | 丁 | 乙 | 丙
丁 | 丁 | | 丁 |
再來就是一點點暴力的樹狀圖: (我的表示法是 人-位置 )
(比如說 甲在三這個位置 那就寫成 甲-3 )
丁-3 -> 乙剩4.5兩個位子 => (2種)
/
丙-1 \
丁-4 -> 乙剩5一個位子 => (1種)
/
甲-2
\
丙-5 -> 乙先選2.4其中一位,丁必還有兩位可選 => (4種)
丙-2 -> 丁剩4一個位子 => (1種)
/
乙-1 \
丙-5 -> 丁剩2.4兩個位子 => (2種)
/
甲-3 - 乙-4 -> 丁先選1.2其中一位,丙必還有兩位可選 => (4種)
\
乙-5 -> 丙先選1.2其中一位,丁必還有兩位可選 => (4種)
丙-2 -> 丁剩3一個位子 => (1種)
/
乙-1 \
/ 丙-5 -> 丁剩2.3兩個位子 => (2種)
甲-4
\
乙-5 -> 丙先選1.2其中一位,丁必還有兩位可選 => (4種)
因為以上甲乙丙丁選完位子後 戊就只有一個位子可以放 所以沒得挑了
因此總共有 2+1+4+1+2+4+4+1+2+4 = 25種
我是因為要把算法打出來
不然如果單純計算稍微畫一下這個樹狀圖其實可以算很快
我覺得應該還比用排容原理加加減減快
以上就是我的算法
不過不確定有沒有算錯
如果有的話希望板友們幫忙指正囉
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.82
推 ntnusliver :25 +1 05/08 18:39
→ jameschou :所以是26嗎@@ 05/08 18:55
推 krauserq :正解25 05/11 09:15