数学建模 比赛日程安排问题 答案及程序代码 |
您所在的位置：网站首页 › 6支队伍篮球赛程安排表图片 › 数学建模 比赛日程安排问题 答案及程序代码 |
数学建模 比赛日程安排问题 答案及程序代码
|
一、 问题
分析： 大意是n支球队，每天只打一场比赛，每支球队相邻的两场比赛至少间隔t天。问这个t最大能是多少？具体如何安排？ 1) 5支球队(0, 1, 2, 3, 4)，至少间隔1天。具体赛程安排如下： 天数队伍1队伍2第1天01第2天23第3天04第4天12第5天34第6天02第7天13第8天24第9天03第10天142) 六支球队(0, 1, 2, 3, 4, 5)，不能间隔两天，那样不能满足每天一场比赛的要求。经验证，t最大为1，即可至少间隔一天。具体赛程安排如下： 天数队伍1队伍2第1天01第2天23第3天04第4天12第5天03第6天14第7天05第8天13第9天25第10天34第11天15第12天24第13天35第14天02第15天45七支球队(0, 1, 2, 3, 4, 5, 6)，可以至少间隔两天，具体赛程安排如下： 天数队伍1队伍2第1天01第2天23第3天45第4天06第5天12第6天34第7天56第8天02第9天14第10天35第11天26第12天04第13天15第14天36第15天24第16天05第17天13第18天46第19天25第20天03第21天163) 答：推广到n支球队，每支球队在两场比赛之间至少可间隔 n 2 − 1 \frac{n}{2}-1 2n−1 (天) 4) 答：考虑到尽量给各球队休息和战术安排的时间，让各队不至于比赛时间太紧，不推荐同一球队两场比赛时间间隔太短。而间隔时间越长，给各球队的休息和战术安排时间就越多。因此，推荐n支球队间隔 n 2 − 1 \frac{n}{2}-1 2n−1 天。 三、 程序代码PS： 我采用的辗转法，每过t天，前面第day-t天的组合就能打了。 然后用了回溯法，因为有的时候，剩下多组队伍，好几个队伍都没互相打过，则该天选哪两组打，对结果的影响很大。如果你选错了，就会出现接下来某一天剩余能打的队伍中，任意两两都已经打过了，则该天就不会满足每天一场的要求。这时候就要回溯到选错的那一天，换一组来打。 而n支球队，两两PK一次，一共能打 n − 1 + n − 2 + . . . + 1 = ( n − 1 ) ∗ n 2 n-1 + n-2 + ... + 1 = \frac{(n - 1) * n}{2} n−1+n−2+...+1=2(n−1)∗n天。所以递归的跳出条件，就是day达到该值。 代码如下： #include #include #include using namespace std; struct game { int l, r; }; vector dp; //周期为t+1内的比赛情况 int n, t; //n支球队，相隔t天 vector arr; //n支球队是否能打 vector *visit; //谁跟谁打过 int sum; //一共可以打几组 int day = 0; //当前为第几天 vector path; //第i天比赛情况 void init() { //输入球队个数n和间隔天数t cout n; cout |
【本文地址】
今日新闻 |
推荐新闻 |