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