数学建模 比赛日程安排问题 答案及程序代码
一、 问题
二、答案
分析:
大意是n支球队,每天只打一场比赛,每支球队相邻的两场比赛至少间隔t天。问这个t最大能是多少?具体如何安排?
1) 5支球队(0, 1, 2, 3, 4),至少间隔1天。具体赛程安排如下:
天数 | 队伍1 | 队伍2 |
---|---|---|
第1天 | 0 | 1 |
第2天 | 2 | 3 |
第3天 | 0 | 4 |
第4天 | 1 | 2 |
第5天 | 3 | 4 |
第6天 | 0 | 2 |
第7天 | 1 | 3 |
第8天 | 2 | 4 |
第9天 | 0 | 3 |
第10天 | 1 | 4 |
2) 六支球队(0, 1, 2, 3, 4, 5),不能间隔两天,那样不能满足每天一场比赛的要求。经验证,t最大为1,即可至少间隔一天。具体赛程安排如下:
天数 | 队伍1 | 队伍2 |
---|---|---|
第1天 | 0 | 1 |
第2天 | 2 | 3 |
第3天 | 0 | 4 |
第4天 | 1 | 2 |
第5天 | 0 | 3 |
第6天 | 1 | 4 |
第7天 | 0 | 5 |
第8天 | 1 | 3 |
第9天 | 2 | 5 |
第10天 | 3 | 4 |
第11天 | 1 | 5 |
第12天 | 2 | 4 |
第13天 | 3 | 5 |
第14天 | 0 | 2 |
第15天 | 4 | 5 |
七支球队(0, 1, 2, 3, 4, 5, 6),可以至少间隔两天,具体赛程安排如下:
天数 | 队伍1 | 队伍2 |
---|---|---|
第1天 | 0 | 1 |
第2天 | 2 | 3 |
第3天 | 4 | 5 |
第4天 | 0 | 6 |
第5天 | 1 | 2 |
第6天 | 3 | 4 |
第7天 | 5 | 6 |
第8天 | 0 | 2 |
第9天 | 1 | 4 |
第10天 | 3 | 5 |
第11天 | 2 | 6 |
第12天 | 0 | 4 |
第13天 | 1 | 5 |
第14天 | 3 | 6 |
第15天 | 2 | 4 |
第16天 | 0 | 5 |
第17天 | 1 | 3 |
第18天 | 4 | 6 |
第19天 | 2 | 5 |
第20天 | 0 | 3 |
第21天 | 1 | 6 |
3) 答:推广到n支球队,每支球队在两场比赛之间至少可间隔 (天)
4) 答:考虑到尽量给各球队休息和战术安排的时间,让各队不至于比赛时间太紧,不推荐同一球队两场比赛时间间隔太短。而间隔时间越长,给各球队的休息和战术安排时间就越多。因此,推荐n支球队间隔 天。
三、 程序代码
PS:
我采用的辗转法,每过t天,前面第day-t天的组合就能打了。
然后用了回溯法,因为有的时候,剩下多组队伍,好几个队伍都没互相打过,则该天选哪两组打,对结果的影响很大。如果你选错了,就会出现接下来某一天剩余能打的队伍中,任意两两都已经打过了,则该天就不会满足每天一场的要求。这时候就要回溯到选错的那一天,换一组来打。
而n支球队,两两PK一次,一共能打天。所以递归的跳出条件,就是day达到该值。
代码如下:
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct game
{
int l, r;
};
vector<game> dp; //周期为t+1内的比赛情况
int n, t; //n支球队,相隔t天
vector<bool> arr; //n支球队是否能打
vector<bool> *visit; //谁跟谁打过
int sum; //一共可以打几组
int day = 0; //当前为第几天
vector<game> path; //第i天比赛情况
void init()
{
//输入球队个数n和间隔天数t
cout << "请输入球队个数n:\n";
cin >> n;
cout << "\n请输入间隔天数t∈[0," << n / 2 - 1 << "]:\n";
cin >> t;
//加上限
if (t > n / 2 - 1)
{
puts("\n间隔天数过多,无法满足每天一场球赛!");
puts("over");
while (1);
exit(0);
}
//数据初始化
sum = n * n; //一共可以打n*n组
arr.resize(n, true); //初始化n支球队都可以打
dp.resize(t + 1); //game结构体长度为循环周期t+1
path.resize(n*(n - 1) / 2 + 1);
//创建邻接矩阵表示n支队伍两两是否打过
visit = new vector<bool>[n];
for (int i = 0; i < n; i++)
{
visit[i].resize(n, false); //初始化为没有打过
}
//第一个比赛周期初始化,0 and 1, 2 and 3, ...
for (int i = 0; i <= t; i++)
{
//他俩不能打了
arr[i << 1] = arr[i << 1 | 1] = false;
//两个人入结构体
dp[i].l = i << 1;
dp[i].r = i << 1 | 1;
//标记两个人已经打过
visit[i << 1][i << 1 | 1] = true;
visit[i << 1 | 1][i << 1] = true;
//总场次-2 (0 and 1, 1 and 0分别算一场),天数+1
sum -= 2;
day++;
//记录
path[day].l = i << 1, path[day].r = i << 1 | 1;
}
//打完t+1天后,第0天的两组又可以打了
arr[0] = arr[1] = true;
};
void fun(int index)
{
if (day == n * (n - 1) / 2)
{ //n支球队一天打一场,最多打 (n-1) + (n-2) + ... + 1 == n * (n - 1) / 2 场
cout << "\n共需比赛" << n * (n - 1) / 2 << "天,比赛日程安排如下:\n\n";
printf("%5s :队伍1\t队伍2\n", "天数");
for (int i = 1; i <= n * (n - 1) / 2; i++)
printf("第%3d天:%2d\t%2d\n", i, path[i].l, path[i].r); //输出比赛日程安排情况
puts("over1");
while (1);
exit(0);
}
for (int i = 0; i < n; i++) //第一个可以打的
{
if (!arr[i]) continue; //跳过不能打的
arr[i] = false; //如果选了他,他暂时就不能再打了
for (int j = i + 1; j < n; j++) //第二个可以打的
{
if (!arr[j] || visit[i][j]) continue; //跳过不能打的和已经与i打过的
arr[j] = false; //如果选了他,他暂时就不能再打了
//标记第index天他俩打过
int left = dp[index].l, right = dp[index].r;
dp[index].l = i;
dp[index].r = j;
//标记两人已经打过
visit[i][j] = true;
visit[j][i] = true;
//总场次-2 (0 and 1, 1 and 0分别算一场),天数+1
sum -= 2;
day++;
//记录
path[day].l = i, path[day].r = j;
//cout << "第" << day << "天:" << i << " " << j << endl;
//已经过t天的人可以打了
arr[dp[(index + 1) % (t + 1)].l] = true;
arr[dp[(index + 1) % (t + 1)].r] = true;
//进入下一天
fun((index + 1) % (t + 1));
//回溯
arr[j] = true; //j: 我还能打!
//标记第index天他俩打过--不是他俩
dp[index].l = left;
dp[index].r = right;
//标记两人已经打过--没打过
visit[i][j] = false;
visit[j][i] = false;
sum += 2; //加回来
day--; //减回来
//已经过t天的人可以打了--今天没打呢,你先别能打的
arr[dp[(index + 1) % (t + 1)].l] = false;
arr[dp[(index + 1) % (t + 1)].r] = false;
}
//回溯,i又能打了
arr[i] = true;
}
}
int main()
{
init();
fun(0);
puts("over2");
while (true);
return 0;
}