PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 大地排關問題

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間10年前 (2014/03/02 21:08)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串4/5 (看更多)

※ 引述《tkcn (sayuan)》之銘言： : 整理一下目前我取得的資訊，雖然說實在還蠻有限的。 : 首先我認為這個問題應該早就有相關的研究， : 所以打算先找相關的文獻，但無奈找不到正確的關鍵字，所以沒進展。 : ps. 『求關鍵字！』 : 後來，想說先從類似的問題開始找起， : 發現 Round-robin tournament (循環賽) 其實蠻像的， : 一樣是 n 個隊伍兩兩交手，且交手過得隊伍不得再次交手。 : 但差別在於，Round-robin torunament 的每一場都是相同的競賽， : 並沒有像是大地遊戲有不同關卡的區分。 : 單純只是要排 Round-robin tournament 的話基本上都有解， : 但要把每一場對戰對應到大地遊戲的關卡時， : 就會發現一支隊伍參與同一個關卡不只一次的狀況。 : 在大地遊戲中，相較於同一個關卡玩兩次， : 遇到相同對手兩次其實不是什麼太大不了的事， : 所以我想從這個方向下手其實不太適合。 : ---- : 接著想說寫程式來跑跑看，看能看能不能得出什麼規律。 : 若狀況是 "n 關 m 小隊" 的話， : 假設每個小隊每回合都必須參與，且玩遍所有關卡， : 並且任意兩個小隊不會重複交手的情況下，不難發現： : 1. 小隊數 m 必為偶數 (否則每回合都有小隊無法配對) : 2. n*2 >= m (否則場地不足所有小隊參賽) : 3. n < m (否則關卡比其他小隊數目還多) : 於是就設計了一個跟原 po 概念一致的 DFS， : 然後跑出了以下結果： : | n\m | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | : |-----|---|---|---|---|----|----|----|----| : | 1 | o | | | | | | | | : | 2 | | x | | | | | | | : | 3 | | x | o | | | | | | : | 4 | | | o | o | | | | | : | 5 | | | x | x | o | | | | : | 6 | | | | x | o | o | | | : | 7 | | | | x | o | o | o | | : | 8 | | | | | o | o | o | o | 這個圖給了我啟發，手動去排排出了一點心得。在 n * 2 = m (n >= 3) 的情況下似乎有速解。以 n = 3, m = 6為例先定出1 2 3 1 2 3 1 2 3 1 2 3 從1行填入456 1 vs 4 2 3 1 vs 5 2 3 1 vs 6 2 3 2行到3行開始將456順序不變的往上推，超過邊界就從另一端補，想像成一個環在轉。 4 5 6 5 6 4 6 4 5 ^ ^ | | ^ | 1 vs 4 2 vs 5 3 vs 6 1 vs 5 2 vs 6 3 vs 4 1 vs 6 2 vs 4 3 vs 5 再來 1 2 3 -> 3 1 2 ->-> 2 3 1 1 vs 4 2 vs 5 3 vs 6 3 vs 5 1 vs 6 2 vs 4 2 vs 6 3 vs 4 1 vs 5 這樣應該就是解了。好像沒什麼幫助(笑)，不過一點小發現就分享出來。 : 留空的部份表示沒有滿足前提， : 而 o, x 當然就是表示有解、無解。 : 嗯，其實看不出什麼規律， : 而 n=8 時，每一組要跑數分鐘，(其他的都是 3 秒以下) : 所以大概也不會再有更多結果了。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.135.203.156