![cover](https://img-blog.csdnimg.cn/011f8849bea14e01a2506d8202e5f64a.png)
算法设计与分析/数据结构与算法实验2:循环赛安排问题
1.实验目的(1)掌握递归与分治法的处理思路与算法框架。(2)掌握应用递归与分治法解决具体问题的方法。(3)掌握分治法的广泛应用。2.实验内容(1)问题描述设有nnn个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表:(1)每个选手必须与其他n−1n-1n−1个选手各赛一次(2)每个选手一天只能赛一次。(3)当nnn是偶数时,循环赛进行n−1n-1n−1天;当nnn是奇数时,循环赛进行nn
视频讲解指路:https://www.bilibili.com/video/BV1Xu4y197GL
1.实验目的
(1)掌握递归与分治法的处理思路与算法框架。
(2)掌握应用递归与分治法解决具体问题的方法。
(3)掌握分治法的广泛应用。
2.实验内容
(1)问题描述
设有
n
n
n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其他
n
−
1
n-1
n−1个选手各赛一次
(2)每个选手一天只能赛一次。
(3)当
n
n
n是偶数时,循环赛进行
n
−
1
n-1
n−1天;当
n
n
n是奇数时,循环赛进行
n
n
n天。
(2)输入
n n n:运动员人数。
(3)输出
一个比赛日程表,为有 n n n行和 n − 1 n-1 n−1列的表。在表中第 i i i行和第 j j j列处填入第 i i i个选手在第 j j j天所遇到的对手。
3.问题实例分析
实例:输入参数9。9是一个奇数,需要安排9天的循环赛。循环赛赛程安排表实现效果如下:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|
2 | 1 | 5 | 3 | 7 | 4 | 8 | 9 | 10 | 6 |
3 | 8 | 1 | 2 | 4 | 5 | 9 | 10 | 6 | 7 |
4 | 5 | 9 | 1 | 3 | 2 | 10 | 6 | 7 | 8 |
5 | 4 | 2 | 10 | 1 | 3 | 6 | 7 | 8 | 9 |
6 | 7 | 8 | 9 | 10 | 1 | 5 | 4 | 3 | 2 |
7 | 6 | 10 | 8 | 2 | 9 | 1 | 5 | 4 | 3 |
8 | 3 | 6 | 7 | 9 | 10 | 2 | 1 | 5 | 4 |
9 | 10 | 4 | 6 | 8 | 7 | 3 | 2 | 1 | 5 |
其中,表有10列。第1列表示选手编号,之后的2~10列中每一列都表示当天的对手。循环赛要安排9天。表格中的“10”并不是真实的对手,而是表示当前选手在当日轮空没有被安排比赛。 | |||||||||
实例中,“9”为奇数。可以加以推广:当我们需要安排 n n n人循环赛时,若 n n n为奇数,我们可以安排 n + 1 n+1 n+1人的循环赛,安排表中若有人与第 n + 1 n+1 n+1号人进行比赛,其实并非真的比赛而表示轮空。若 n n n为偶数,则可以将所有选手分为两半, n n n个选手的比赛日程表可以通过设计 n / 2 n/2 n/2人的循环赛日程表决定。 | |||||||||
在设计完成 n / 2 n/2 n/2人的循环赛日程表后,左上角与左下角分别为选手1至选手 n / 2 n/2 n/2以及选手 n / 2 + 1 n/2+1 n/2+1至选手 n n n前 n / 2 − 1 n/2-1 n/2−1天的比赛日程。选手 n / 2 + 1 n/2+1 n/2+1至选手 n n n前 n / 2 − 1 n/2-1 n/2−1天的比赛日程为左上角选手1至选手 n / 2 n/2 n/2的比赛日程复制后加上 n / 2 n/2 n/2得到。将左上角小块中的所有数字按其相对位置复制到右下角,将左下角小块中的数字按其相对位置复制到右上角,这样就分别安排好了。 | |||||||||
所以,为了设计9人循环赛,可以先设计10人循环赛。为了设计10人循环赛,可以先设计5人循环赛。为了设计5人循环赛,可以先设计6人循环赛。以此类推,设计3人、4人、2人循环赛。 | |||||||||
二人循环赛安排如表所示。 | |||||||||
1 | 2 | ||||||||
– | – | ||||||||
2 | 1 | ||||||||
在安排完成2人循环赛后,4人循环赛也可以进行安排。其中,右下角部分与左上角部分是相同的。左下角部分是的设计办法如下:按相对位置,将左上部分的对应值 + n / 2 +n/2 +n/2。右上角部分与左下角部分是相同的。右上角部分与左下角部分是相同的。这一过程可以被封装成copyeven函数。 | |||||||||
1 | 2 | 3 | 4 | ||||||
– | – | – | – | ||||||
2 | 1 | 4 | 3 | ||||||
3 | 4 | 1 | 2 | ||||||
4 | 3 | 2 | 1 | ||||||
接下来,将4视为轮空,3人循环赛安排表与4人循环赛安排是一致的。 | |||||||||
1 | 2 | 3 | 4 | ||||||
– | – | – | – | ||||||
2 | 1 | 4 | 3 | ||||||
3 | 4 | 1 | 2 | ||||||
通过3人循环赛安排,可以安排出6人循环赛。但是,奇数人数循环赛的“复制”、“抄”的过程与偶数人数循环赛复制过程有一定区别且较为复杂。这一过程可以被封装成copyodd函数。 | |||||||||
对于左下部分,在把左上位置复制到左下并按相对位置加上 n / 2 n/2 n/2后,还需要安排轮空选手。在例如,1号轮空对应4号也轮空。2号轮空对应5号也轮空。3号轮空对应6号轮空。 i i i轮空对应 i + n / 2 i+n/2 i+n/2轮空,则安排这两个选手比赛。可以用一个数组 b n b_n bn记录轮空选手的对应情况。 b i = ( i + 2 ) m o d n b_i=(i+2)\mod n bi=(i+2)modn。至此,左上部分与左下部分已经安排完成。 | |||||||||
对于右上部分,注意到前 n / 2 n/2 n/2个选手在前 n / 2 n/2 n/2天除了与上文所述的对应轮空选手比赛,并未与其他的后 n / 2 n/2 n/2的选手进行过比赛。所以,第 i i i号选手第 n / 2 + j n/2+j n/2+j天与第 b i + j − 1 b_{i+j-1} bi+j−1号选手比赛。例如,1号第4天与5号比赛,第5天与6号比赛;2号第4天与6比赛,第5天与4比赛。以此类推。 | |||||||||
对于右下部分,是后 n / 2 n/2 n/2个选手后 n / 2 n/2 n/2天的赛程。但在安排右上部分循环赛时,前 n / 2 n/2 n/2号选手被安排的选手都是后 n / 2 n/2 n/2号选手。所以右下部分取决于右上部分。 | |||||||||
至此,分析了 n / 2 n/2 n/2为奇数时的循环赛扩展、复制为 n n n人循环赛时的办法。注意:是 n / 2 n/2 n/2为奇数不是 n n n为奇数!!! |
1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|
2 | 1 | 5 | 3 | 6 | 4 |
3 | 6 | 1 | 2 | 4 | 5 |
4 | 5 | 6 | 1 | 3 | 2 |
5 | 4 | 2 | 6 | 1 | 3 |
6 | 3 | 4 | 5 | 2 | 1 |
通过类似的办法,就能安排5人循环赛、10人循环赛了。 | |||||
1 | 2 | 3 | 4 | 5 | 6 |
– | – | – | – | – | – |
2 | 1 | 5 | 3 | 6 | 4 |
3 | 6 | 1 | 2 | 4 | 5 |
4 | 5 | 6 | 1 | 3 | 2 |
5 | 4 | 2 | 6 | 1 | 3 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|
2 | 1 | 5 | 3 | 7 | 4 | 8 | 9 | 10 | 6 |
3 | 8 | 1 | 2 | 4 | 5 | 9 | 10 | 6 | 7 |
4 | 5 | 9 | 1 | 3 | 2 | 10 | 6 | 7 | 8 |
5 | 4 | 2 | 10 | 1 | 3 | 6 | 7 | 8 | 9 |
6 | 7 | 8 | 9 | 10 | 1 | 5 | 4 | 3 | 2 |
7 | 6 | 10 | 8 | 2 | 9 | 1 | 5 | 4 | 3 |
8 | 3 | 6 | 7 | 9 | 10 | 2 | 1 | 5 | 4 |
9 | 10 | 4 | 6 | 8 | 7 | 3 | 2 | 1 | 5 |
10 | 9 | 7 | 5 | 6 | 8 | 4 | 3 | 2 | 1 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|
2 | 1 | 5 | 3 | 7 | 4 | 8 | 9 | 10 | 6 |
3 | 8 | 1 | 2 | 4 | 5 | 9 | 10 | 6 | 7 |
4 | 5 | 9 | 1 | 3 | 2 | 10 | 6 | 7 | 8 |
5 | 4 | 2 | 10 | 1 | 3 | 6 | 7 | 8 | 9 |
6 | 7 | 8 | 9 | 10 | 1 | 5 | 4 | 3 | 2 |
7 | 6 | 10 | 8 | 2 | 9 | 1 | 5 | 4 | 3 |
8 | 3 | 6 | 7 | 9 | 10 | 2 | 1 | 5 | 4 |
9 | 10 | 4 | 6 | 8 | 7 | 3 | 2 | 1 | 5 |
4.算法描述及说明
若
n
>
2
n>2
n>2且为奇数,则先安排
n
+
1
n+1
n+1人循环赛。若
n
>
2
n>2
n>2且为偶数,则先递归地安排
n
/
2
n/2
n/2人循环赛。
在安排完
n
/
2
n/2
n/2人循环赛后,若
n
/
2
n/2
n/2为偶数(注意:是
n
/
2
n/2
n/2为偶!不是n为偶!),则执行copyeven()函数将
n
/
2
n/2
n/2人循环赛安排表扩展成
n
n
n人循环赛。若
n
/
2
n/2
n/2为奇数(注意:是
n
/
2
n/2
n/2为奇!不是n为奇!此时
n
n
n为偶数!),则执行copyodd()函数将
n
/
2
n/2
n/2人循环赛安排表扩展。copyeven与copyodd函数见实例分析。算法流程图如下。
若
n
n
n为2,则直接安排2人循环赛,算法结束。
5.算法正确性分析
利用数学归纳法。
n
=
2
n=2
n=2时循环赛安排表存在。对于
n
=
k
n=k
n=k,假设
k
k
k人循环赛安排表存在。若
k
k
k为奇数,则
k
+
1
k+1
k+1人循环赛安排表存在。若
k
k
k为偶数,则
2
k
2k
2k和
2
k
−
1
2k-1
2k−1人循环赛安排表存在。
举例:当2人循环赛安排存在时,3人和4人循环赛也存在。3人循环赛安排存在时,5人和6人循环赛也存在。4人循环赛安排存在时,7人和8人循环赛安排也存在。以此类推。
6.算法时间复杂性分析
设
T
(
k
)
T(k)
T(k)是算法覆盖安排
k
k
k人循环赛所需的时间。
T
(
k
)
T(k)
T(k)满足如下递归方程:
解此递归方程可得
T
(
k
)
=
O
(
n
2
)
T(k)=O(n^2)
T(k)=O(n2),算法是渐进意义下的最优算法。
7.运行结果展示及其说明
测试样例:根据提示输入人数11,则正确地生成了11人循环赛的安排表。
8.心得体会
9.程序源代码
#include<iostream>
#include<iomanip>
using namespace std;
const int M = 105;
int arr[M][M];
int brr[M];//轮空选手对应情况数组
int N;
void print(int n) {//输出
if (n % 2 == 0) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n ; j++)
cout << setw(3) << arr[i][j];
cout << endl;
}
cout << endl;
return;
}
if (n % 2 == 1) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n +1; j++)
cout << setw(3) << arr[i][j];
cout << endl;
}
cout << endl;
return;
}
}
void copyeven(int n) {//偶数人数时的复制
int m = n / 2;
for(int i=1;i<=m;i++)
for (int j = 1; j <= m; j++) {
arr[i][j + m] = arr[i][j] + m;//复制右上角
arr[i + m][j] = arr[i][j + m];//复制左下角
arr[i + m][j + m] = arr[i][j];//复制右下角
}
}
void copyodd(int n) {//奇数人数时的复制
int m = n / 2;
for (int i = 1; i <= m; i++) {//计算轮空选手对应情况
brr[i] = m + i;
brr[m + i] = brr[i];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m + 1; j++) {
if (arr[i][j] > m) {//arr[i][j]>=m+1,当前选手轮空
arr[i][j] = brr[i];
arr[m + i][j] = (brr[i] + m) % n;//安排轮空选手进行对战
}
else
arr[m + i][j] = arr[i][j] + m;//不轮空的情况,左下角直接复制
}
for (int j = 2; j <= m; j++) {
arr[i][m + j] = brr[i + j - 1];//右上角安排选手
arr[brr[i + j - 1]][m + j] = i;//右下角安排选手
}
}
}
void copy(int n) {
if (n / 2 > 1 && ((n /2)%2 == 1))//根据n/2为奇数或偶数选择copyodd或copyeven
copyodd(n);
else copyeven(n);
}
void work(int n) {
if (n == 1) {
arr[1][1] = 1;
return;
}//递归边界
if (n % 2 == 1) {
work(n+1);//奇数人,安排n+1人循环赛
return;
}
work(n / 2);//安排n/2人循环赛
copy(n);//复制
}
int main() {
cin >> N;
work(N);
print(N);
}
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)