發新話題
打印

答案很小的排列組合問題是用窮舉還是扣除比較快?

推到噗浪
推到臉書

答案很小的排列組合問題是用窮舉還是扣除比較快?

(標題怎麼那麼容易超過80字節?)
「甲乙丙丁戊圍一圓桌而坐,甲乙相鄰,且丙丁相鄰,且甲戊不相鄰,共有幾種坐法?」是用窮舉比較快,還是扣除比較快得到答案?謝謝!
順帶一問,答案是不是4?
甲乙戊丙丁、甲乙戊丁丙、乙甲丁丙戊、乙甲丙丁戊

TOP

回復 1# 克勞棣 的帖子

窮舉出 5! / 5 = 24 種,就要花很多時間;
應該用扣除會比較快:
所求坐法數
= n( 甲乙鄰 且 丙丁鄰 ) - n( 甲乙鄰 且 丙丁鄰 且 甲戊鄰 )
= n( 甲乙鄰 且 丙丁鄰 ) - n( 丙丁鄰 且 甲在乙戊中間 )

令 A = 甲乙(想像成兩人綁一起) , B = 丙丁 , C = 甲乙戊,甲在乙戊中間
則 n(A) = n(B) = n(C) = 2

所求坐法數
= n( AB戊 ) - n( BC )
= ( 3! / 3 )*2*2 - ( 2! / 2 )*2*2
= 8 - 4
= 4 ..... Ans

TOP

回復 2# Lopez 的帖子

呃......我所謂的「窮舉」不是把未限定任何條件、最原始的「所有」方法數都列出來,然後再把不符合條件者一一剔除,而是要結合「推理」(當然,這要答案不大才有效益)。我們用窮舉解三階幻方(註)也不必把9!種排列都列出來吧!?數獨與蟲蛀算也是要靠推理,不單只是計算。
註:也就是
294
753
618

比方下面2題敝人也不會算它的排列數,可是我知道答案:
「甲乙丙丁圍一圓桌而坐,甲乙不相鄰,且丙丁相鄰,共有幾種坐法?」
「甲乙丙丁圍一圓桌而坐,甲乙相鄰,且丙丁相鄰,且乙丙不相鄰,共有幾種坐法?」

最後仍然要誠懇感謝您的熱心、即時、正確的解答與意見。我佩服您。

TOP

發新話題