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