推 LPH66 : 加法原理的前提: 各個選擇是「互斥」的 11/02 04:17
→ LPH66 : 在 C D E F 中選不是互斥, 但在 P Q 中選是互斥 11/02 04:18
※ 引述 《plok0202 (pl)》 之銘言：
:
:
: 還有這題
: https://i.imgur.com/kwYDbfL.jpeg
: 為什麼不能經過CDEF這些點一定要P或Q
: ACB
: ADB
: ARB
: AFB
:
可以，但是如果你算出
經過C有c種走法
經過D有d種
經過E有e種
經過F有f種
那答案是c+d+e+f嗎？
不是！
因為經過C也經過D的路線算了2次
經過C也經過D也經過F的算了3次
...(以下還有很多種重複的case，略）
還有CDEF都沒經過的路線沒算到！
所以討論經過C,D,E,F的路線有幾種，不會讓題目變簡單，只是變更複雜，仔細算一定算得
出來，答案不會變，只是更難算而已。
那如果看P, Q兩個點：
1. 從A到B經過第二象限的最短路徑一定會經過P或Q （只要設法畫一條通過第二象限，但不
經過P也不經過Q的最短路線就知道為什麼畫不出來）
2. 如果A走到P，要再繞到Q就會繞遠路
，如果先走到Q，要再繞到P，也一定會繞遠路。
所以：經過P的路線一定不會經過Q，經過Q的路線就不會經過P。
1跟2合起來，就知道從A經過第二象限走到B的最短路線，不是只經過P，就是只經過Q，不會
兩個都經過，也不會兩個都沒經過，沒有例外！
所以只要算出經過P的路徑有p條，經過q的路徑有q條，答案就是p+q，不會多算也不會少算
！
至於p,q怎麼算，你先想想看，如果不會我再說明
最後跟原PO說：這種題目沒有為什麼要這樣算，只有算了以後發現這樣比較好算，解答只是
寫出最好算的那一種給你看。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.11.15 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1730485649.A.7A8.html