题目
循环赛日程表的设计:
设计一个满足以下要求的比赛日程表(n=2k):
(1)每个选手必须与其他n-1个选手各赛一次;
(2)每个选手一天只能赛一次;
(3)循环赛一共进行n-1天。
要求:输入选手的数量,需要有效性检查,满足n=2k条件,以矩阵形式输出循环赛日程表。
输出:
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
2 |
1 |
4 |
3 |
6 |
5 |
8 |
7 |
3 |
4 |
1 |
2 |
7 |
8 |
5 |
6 |
4 |
3 |
2 |
1 |
8 |
7 |
6 |
5 |
5 |
6 |
7 |
8 |
1 |
2 |
3 |
4 |
6 |
5 |
8 |
7 |
2 |
1 |
4 |
3 |
7 |
8 |
5 |
6 |
3 |
4 |
1 |
2 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
算法设计描述
由题可知,该赛程表中共n行n列,结构可选取二维数组来操作,其中第i行表示第i个选手的日程表,第一列是选手位列,其余第j列表示第j天遇到的对手。所以实际上我们需要的是n-1列。利用分治策略的思想,我们可以将所有选手分成两半,则n名选手的赛程可由名选手来决定(从颜色区块就可以看出,矩阵是呈对角线对称的,左上角和右下角一致,右上角和左下角一致)。再递归地继续划分选手,直到将问题规模缩小至2位选手时,我们就可以直接让他们比赛即可。
大致思路图:
代码
#include <iostream>
#include <vector>
using namespace std;
void printData(vector<vector<int> >& map)
{
// C++刚学不太熟练,练练迭代器qwq
vector<vector<int> >::iterator outerP;
vector<int>::iterator innerP;
for(outerP = map.begin(); outerP != map.end(); outerP++){
for(innerP = (*outerP).begin(); innerP != (*outerP).end(); innerP++){
cout << *innerP << " ";
}
cout << endl;
}
cout << "\n";
}
// x和y用来存放每次划分所得矩阵的左上角顶点位置,k存储矩阵的行列数
void partition(vector<vector<int> >&map, int x, int y, int k)
{
// 递归终止条件
if(k == 1) return;
// 划分并填充左上角
partition(map,x,y,k/2);
// 划分并填充右上角
partition(map,x,y+k/2,k/2);
for(int i = 0; i < k/2; i++){
for(int j = 0; j < k/2; j++){
// 将左上角复制到右下角
map[x+i+k/2][y+j+k/2] = map[x+i][y+j];
// 将右上角复制到左下角
map[x+i+k/2][y+j] = map[x+i][y+j+k/2];
}
}
}
int main()
{
cout << "请输入选手数量n,要求满足n = 2^k :";
int flag = 1;
int n = 0;
// 有效性检查,输入有误则要求用户重新输入
while(flag){
cin >> n;
// 如果输入的值与定义的变量类型不同,cin.fail()为真
if(cin.fail() || n%2 != 0){
cout << "您的输入有误,请重新输入!\n";
cin.clear();//清除了fail错误
cin.ignore();//清除缓冲区内的错误字符
}else
flag = 0;
}
// 建立二维数组存放赛程表
vector<vector<int> > map(n,vector<int>(n));
// 初始化第一行为1~n,则第一名选手的赛程已安排好
for(int i = 0; i < map.size(); i++){
for(int j = 0; j < map[0].size(); j++){
map[0][j] = j+1;
}
}
partition(map,0,0,n);
printData(map);
return 0;
}
实验结果