Re: [運算] 不盡相異物的排列
※ 引述《t007123 (林英傑後援會!!!)》之銘言：
: 依照PAPER最後想得到的結果 是不行的
: 我舉個例子好了
: A
: □
: B C
: □ □
: D E
: □ □
: 這是個五個箱子圍成的正五邊形 也就是環狀排列的
: 現在要將數字1~25 "依序"放進箱子
: 而放進箱子的規則為 如果一開始 1 放入 A 則接下來 2 "只能"放進 B or C
: 也就是只能放相鄰的箱子 但每個箱子放的數量不線
: PAPER上是說
: 他們可以找到一組解 使得 每一個箱子加起來的數字和都是一樣的
: 但並沒有說他是唯一解 而且解還可以畫出漂亮的圖形(這裡就不談了)
呃.. 好吧, 接下來要講的東西,
可能複雜一下.
我先問一下: 你是高中生, 大學生, 或是研究生?
你對於 圖論有概念嗎?
學過 algorithm 嘛?
你得要有一些概念才能做這個方法.
這是一個 ring, 你在這上面繞, 最後算 node 上面的 weight.
繞的方法有非常多種, 人家提過了.
你要找的是 , weight 相同的情況.
我想應該可以用 network flow 來做,
或是 一些 approximate 的方法來解.
最後, 簡單的猜測, 我看到至少兩個方法
你就順時針 繞完 - 逆時針 繞
或是 pair-wise 對 繞 , 都是答案.
: 因為科展需要 老師想跑出所有的解出來看看
: 於是要我去試著寫程式 但後來我想一想 好像有2^25種解
: 暴力解根本不可行 何況還想玩6邊形7邊形
: 所以我們正在想可不可以循別種方法解題
: 基本上這題目陷入膠著 高中生科展好難 orz
N 邊型都能用我上面的那兩種繞法.
--
趙客縵胡纓，吾鉤霜雪明。銀鞍照白馬，颯沓如流星。
十步殺一人，千里不留行。是了拂衣去，深藏身與名。
閑過信陵飲，脫劍膝前橫。將炙啖朱亥，持觴勸侯贏。
三杯吐然諾，五嶽倒為輕。眼花耳熱後，意氣素霓生。
就趙揮金錘，邯鄲先震驚。千秋二壯士，烜赫大梁城。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.170.76.14
→
12/05 15:45, , 1F
12/05 15:45, 1F
推
12/05 18:39, , 2F
12/05 18:39, 2F
→
12/05 18:40, , 3F
12/05 18:40, 3F
討論串 (同標題文章)