※ 引述《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