Re: [其他] TC題 (5) 排列組合 (Sol)
※ 引述《TimcApple (肥鵝)》之銘言:
: Problem 5
: 從 A 點出發,先往 B 點走
: 然後一筆畫走完所有路徑,最後回到 A 點
: 請問有多少種不同的路徑?
: https://i.imgur.com/zDq9mOm.png
如 LPH66 所言,本題的AB點設計只是為了不要重複數圈
將其拔掉比較容易使用對稱性計算
本題大原則就是要將圖形切成小塊來計算路徑
Solution to Problem 5
<Sol 1>
目前最快的解法我很晚才想到,參考了 Sol 3 和 Sol 4 的做法
https://i.imgur.com/YNdSCkj.png
關鍵是用遞迴,一次拆一個三角形
<Sol 2>
LPH66 的解法
https://tinyurl.com/y9aa85yl
用正中央的點 E 當成分類項,總共要經過 3 次 E 點
由此判斷外圍路徑要如何分拆成三組
<Sol 3>
FB 上 Kawai Wong 的作法是遞迴暴力硬拆
https://reurl.cc/5lboAz
另外,他有提供 matlab 的程式解
https://reurl.cc/NjNXek
<Sol 4>
我個人原本的作法,一樣是拆角落的三個小正三角形
然後用中間的連線模式,畫樹狀圖討論
分了 7 個 case,每個 case 最少分三叉,每條路 3 樹枝
實在有點太冗長了就省略了XD
總之,答案應為 4032 種連線數ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.48.74 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1589814322.A.3E7.html