|
问题描述
问题描述：
设有n=2^k 个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他n-1个选手各赛一次；
(2)每个选手一天只能参赛一次；
(3)循环赛在n-1天内结束。
设计思路
设计思路：建立二维数组a[N][N]，存放1-N名运动员的循环赛事情况。初始化为0；当day从1->N时，遍历数组，当二维数组元素a[i][j]行不等于列且所存储元素为0时，遍历a[i][N]和a[N][j]，如果a[i][N]和a[N][j]所储存元素均不包含day，则另a[i][j]=day；循环结束后输出a[N][N]，然后按照day从1-N的顺序输出表a[N][N]中对战情况
数据结构
N=2^k=8：比赛人数
a[N][N]：存放运动员日程安排结果
x[N],y[N]：工作数组，分别存放第i行j列的安排情况
算法描述：
CYCLE RACE(N, a[N][N], x[N], y[N])
- For i=0 to N-1, j=0 to N-1
- a[i][j] <-0
- for day=1 to N
- for i=1 to N, j=1 to N
- If(search(i, j, day, a)=0 and i!=j and a[i][j]=0)
- then a[i][j] =day, a[j][i]=day;
- Output(a)
SEARCH (i, j, day, a)
- For k=0 to N-1
- x[k]<-a[i][k], y[k]<-a[k][j]
- For k=0 to N-1
- If(x[k]=day or y[k]=day)
- then return 1
- Return 0
测试用例及结果说明
运动员人数：N=8
测试结果：
运动员对战情况表：（以8个人为例）
0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0
比赛日程安排结果为
第1天的比赛安排为
队员1 对战 队员2 队员3 对战 队员4 队员5 对战 队员6 队员7 对战 队员8
第2天的比赛安排为
队员1 对战 队员3 队员2 对战 队员4 队员5 对战 队员7 队员6 对战 队员8
第3天的比赛安排为
队员1 对战 队员4 队员2 对战 队员3 队员5 对战 队员8 队员6 对战 队员7
第4天的比赛安排为
队员1 对战 队员5 队员2 对战 队员6 队员3 对战 队员7 队员4 对战 队员8
第5天的比赛安排为
队员1 对战 队员6 队员2 对战 队员5 队员3 对战 队员8 队员4 对战 队员7
第6天的比赛安排为
队员1 对战 队员7 队员2 对战 队员8 队员3 对战 队员5 队员4 对战 队员6
第7天的比赛安排为
队员1 对战 队员8 队员2 对战 队员7 队员3 对战 队员6 队员4 对战 队员5
设计及测试过程
第一步：提出问题；
第二步：问题转换；
第三步：算法构思；
第四步：伪码描述；
第五步：代码编写；
第六步：代码测试；
第七步：代码修正；
参考资料：《c ++程序设计教程》高等教育出版社
评价和改进
算法优点：可以排出所有运动员的对战安排表和日程安排表
算法缺点：遍历的方式使得算法时间和空间花费较大，所列出的解不是活动安排的所有解
附：源程序
#include<iostream>
using namespace std;
#define N 8 //运动员人数，可根据实际自行调整
int search(int i,int j, int day, int a[N][N])
{
int x[N], y[N], k;
for(k=0;k<N;k++)
{
x[k]=a[i][k];
y[k]=a[k][j];
}
for(k=0;k<N;k++)
{
if(x[k]==day||y[k]==day)
return 1;
}
return 0;
}
int main()
{
int a[N][N], i, j, day, x[N], y[N], k;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
a[i][j]=0;
for(day=1;day<N;day++)
{
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(search(i,j,day,a)==0&&i!=j&&a[i][j]==0)
{
a[i][j]=day;
a[j][i]=day;
}
}
cout<<"运动员对战情况表：（以8个人为例）"<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
cout<<"比赛日程安排结果为"<<endl;
for(k=1;k<N;k++)
{
cout<<"第"<<k<<"天的比赛安排为"<<endl;
for(i=0;i<N;i++)
for(j=i;j<N;j++)
if(a[i][j]==k)
cout<<"队员"<<i+1<<" 对战 队员"<<j+1<<" ";
cout<<endl;
}
system("pause");
return 0;
}
| 
转播
