Re: [其他] 求助闖關遊戲分組問題(五家闖六關)
※ 引述《marlborogirl (我不宅，只是愛家)》之銘言：
: 標題: [其他] 求助闖關遊戲分組問題(五家闖六關)
: 時間: Sat Dec 24 12:56:57 2011
:
:
: 以前都是逛版，第一次發文來求助...解釋不清楚的地方還請多包涵...
:
: 是這樣的，因為系上要辦闖關遊戲，被分組問題搞得很頭痛。
: 總共有五個家族，一家分為兩小隊去闖關
: (1a.1b / 2a.2b / 3a.3b / 4a.4b / 5a.5b)
:
: 總共有六關，每關卡闖關時間相同，也就是說六個時段中各要有一關輪流閒置。
:
: 條件1 : 每個小隊都要闖到6關
: 條件2 : 每個小隊不能打自己家 (如1a與1b不能對到)
: 條件3 : 最多只能與重複的小隊對到1次 (如1a與2b不能在第一關與第三關相遇後，就不能再對上)
:
:
: 自己解題過程 :
: 第一次解到一半就發現1a會對上1b (同家族會對上)
: 之後好不容易錯開所有家族、讓每隊玩到每關，卻還是會對到重複的小隊
:
: 1 : x . 5a3b . 4a1b . 3a4b . 2b5b . 1a2a
: 2 : 1a5b . x . 5a2b . 4a3b . 2a1b . 3a4b
: 3 : 2a1b . 1a4b . x . 2b5b . 3a4a . 5a3b
: 4 : 3a2b . 2a5b . 1a3b . x . 5a4b . 4a1b
: 5 : 4a3b . 3a1b . 2a4b . 1a5a . x . 2b5b
: 6 : 5a4b . 4a2b . 3a5b . 2a1b . 1a3b . x
:
: 結果如上，每個小隊重複對到同樣小隊有的甚至高達3次…..
: 希望版上的神人們可以幫幫我 (我數學真的太爛了………..)
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 114.27.39.242
: 推 jass970991 :我覺得無解 12/24 23:16
: → jass970991 :喔幹 我看錯了 12/24 23:18
原理：
http://en.wikipedia.org/wiki/Edge_coloring
節錄：
"A complete graph Kn with n vertices may have its edges colored with
n-1 colors when n
is an even number; this is a special case of Baranyai's theorem.
Soifer (2008) provides the following geometric construction of a coloring in
this case:
place n points at the vertices and center of a regular (n-1)-sided polygon.
For each color class, include one edge from the center to one of the polygon
vertices, and all of the perpendicular edges connecting pairs of polygon
vertices."
K_10的版本：
先把10隊對到10個點，擺好，一個擺中心，其他九個擺一圈：
5b
4b ---+--- 4a
|
3b -----+------- 3a
5a
2b ------------ 2a
1b -------- 1a
這個配對法包含了所有不能採用的對決組合。
也因此，換句話說，其他的對決都可用了。
把這個配對法進行”輪擺式位移”，轉360/9度；
就得到：
5a <-> 4a
5b <-> 3a
4b <-> 2a
3b <-> 1a
2b <-> 1b
這樣的一個配對法。
以此類推，事實上，可以得到八個配對法可用來排關卡。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 182.235.189.13
→
12/25 03:44, , 1F
12/25 03:44, 1F
→
12/25 03:46, , 2F
12/25 03:46, 2F
→
12/25 03:47, , 3F
12/25 03:47, 3F
→
12/25 04:58, , 4F
12/25 04:58, 4F
其實可以看看有沒有資工系的朋友，請他們花時間寫程式，幫你硬爆一下；
就算跑完，真的無解，也可以認命，進而尋求其他解決方法。 XD
真的要追求完美的話，又找不到認識的人的話，
看要不要出點小錢，找人寫程式，確認結果。
（Code寫好，就是放著電腦跑一跑，結果就出來了。）
其他解決方法有：比方說加一關之類的，就我設計過大地遊戲這種營隊活動的經驗而言，
省事的方法就是加一關，這樣整個跑關的調度會充裕不少。
營隊遊戲其實好玩就好，不一定要求每隊玩的內容一定都要一樣。
※ 編輯: Eeon 來自: 182.235.189.13 (12/25 17:06)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：