※ 引述《j19951102 (j19951102)》之銘言： : http://www.nknu.edu.tw/~ns/country/2005first-test.doc : 這個網站上的第12題 : 還有 : http://www.nknu.edu.tw/~ns/country/2005second-team-test.doc : 這個網站上的第二題 : 兩個是類似的 : 希望能說說如何數，或是否有通解 : 感覺上是用遞迴 : 但不知如何下手 目前只整理出上面那題簡易版,筆者一定是瘋了才會半夜還在想=.= 請先將中間那個六邊形的下方頂點設為C,左上角設為D,右上角設為E 其實所有的路徑主要都跟這三個頂點有關係 接下來我們分析路徑的長度,因為ABCDE這五個點中彼此近距離相鄰 的連通路徑都是兩個邊(這裡還沒考慮繞來繞去),所以答案中所有路 徑的長度應該都是偶數,這個部分只是稍微提及一下方便等一下數路 徑. 最後我們開始列出路徑: (1) A - C - B ,路徑長度4 (這是最短路徑) 很容易看出就是底下兩個菱形,路徑數 = 2 x 2 = 4種 (2) A - D - C - B 與 A - C - E - B ,路徑長度6 這兩種類似所以列在一起,因為 A - D - C 與 C - E - B 路徑 數都是3種,而 C - B 與 A - C 都是2種,因此路徑數小計 = 12種 (3 x 2 + 2 x 3 = 12) (3) A - D - E - B ,路徑長度6 這種也很簡單,因為每一段路徑數都是2種,所以 2 x 2 x 2 = 8 (4) A - C - D - E - B ,路徑長度8 以下開始比較複雜,式子不好列,希望筆者寫的大家可以看懂orz : (i) A - C -(左)- D - E - B ^^^^^^^^^^^^^^ 1 x 2 x 2 = 4 (ii) A - C -(上)- D - E - B ^^^^^^^^^^^^^^ 2 x 1 x 2 = 4 (此區小計8種) (5) A - D - C - E - B ,路徑長度8 (i) A - D -(右)- C - E - B ^^^^^^^^^^^^^^ 2 x 1 x 1 = 2 (ii) A - D -(下) - C - E - B ^^^^^^^^^^^^^^^ ^^^^^^^^^ 1 x 3 = 3 (此區小計5種) (6) A - D - E - C - B ,路徑長度8 (i) A - D -(右上) - E - C - B ^^^^^^^^^^^^^^^^^ ^^^^^^^^^ 2 x 1 x 3 = 6 (ii) A - D -(右下) - E - C - B ^^^^^^^^^^^^^^^^^ 2 x 1 x 1 x 1 = 2 (此區小計8種) 綜合(1)~(6) , 路徑總數 = 4 + 12 + 8 + 8 + 8 + 5 = 45種 不是多好的方法,僅供參考 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.166.166.220