給出跑不完結果的程式:
http://pastie.org/8812754
http://ideone.com/0aZL0G
對戰組合狀態24個,加上(6-8/2)*6=12個休關,總數36
基本上一開始產生狀態就不要考慮會重複。
也就是產生不重複的所有狀態再加上休關共36個。
程式執行結果:
list size is 24
1_8
1_7
1_6
1_5
1_4
1_3
2_8
2_7
2_6
2_5
2_4
2_3
3_8
3_7
3_6
3_5
4_8
4_7
4_6
4_5
5_8
5_7
6_8
6_7
sleep
sleep
sleep
sleep
sleep
sleep
sleep
sleep
sleep
sleep
sleep
sleep
total need 36
6
(cpu i7-3770,5分鐘連6個時段都跑不完)
代碼很簡單,有寫錯或問題可以提出討論。
程式可以提供進行修改。
※ 引述《qaz00123 (00123)》之銘言:
: 本身不是資工系但是以前有稍微接觸演算法
: 最近剛好營隊要排對戰表想說自己來寫寫看
: 大概規則是 ( 文字表達能力薄弱orz 文末附上對戰表的大概樣子 )
: n關 m小隊
: 總共有n個時段,
: 每小隊都要玩到每一關,
: 每個時段中每關要有兩個小隊在同一關
: 同個時段不可以有小隊同時出現在不同的兩關
: 每關會休關 n-m/2 個時段
: 盡量不重複對上之前對過的小隊
: 目前想法是用DFS慢慢找
: 每找到一組可行的解就記錄對上重複小隊的次數
: 然後找最小的。
: 想問問看有沒有更好的方法?
: ( 雖然我還在磨DFS要怎麼實做出來orz )
: ======================================================
: 對戰表大概是 (假設是六關八小)
: 時段一 時段二 時段三 時段四 時段五 時段六
: 第一關 1vs2 休關 休關
: 第二關 3vs4 休關 休關
: 第三關 休關 休關
: 第四關 5vs6 休關 休關
: 第五關 7vs8 休關 休關
: 第六關 休關 休關
: ======================================================
: 先謝謝大家:D