网球循环赛算法分析与设计(C++)

编程入门行业动态更新时间:2024-10-13 18:24:15

网球<a href=https://www.elefans.com/category/jswz/34/1620323.html style= 循环赛算法分析与设计(C++)"/>

网球循环赛算法分析与设计(C++)

设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表：

1）每个选手必须与其他n-1个选手各赛一次

2）每个选手一天只能赛一次

3）当n是偶数时，循环赛进行n-1天。当n是奇数时，循环赛进行n天

书中对于 2 k 2^k 2k 的运动员的赛程安排在这里便行不通了，所以需要考虑新的办法。

如果当n为奇数时，可以考虑补充一个虚拟对手，即让n+1为偶数，多出的虚拟对手，代表轮空。

接下来考虑如果n/2为偶数，则可以同 2 k 2^k 2k一样的方法来进行填充，而如果n/2为奇数的话，需要进行新的处理。

综上，下面以n=6为例说明算法：

#define rep(i,s,n) for(int i=s;i<n;i++) //循环
void tournament(int n)
{if (n == 1){a[n][n] = 1;return;}if (n % 2 == 1)//奇数{tournament(n + 1);return;}tournament(n / 2);match_copy(n);}

主递归函数，先判断n是否为奇数，如果为奇数，则转换为求解n+1的问题

void match_copy(int n)
{if (n / 2 > 1 && odd(n / 2))copyodd(n);elsecopy(n);}

考虑n/2的奇偶性，分别做出处理

void copy(int n)
{int m = n / 2;for (int i = 1; i <= m; i++){for (int j = 1; j <= m; j++){a[i][j + m] = a[i][j] + m;a[i + m][j] = a[i][j + m];a[i + m][j + m] = a[i][j];/*rep(i, 1, 9) {rep(j, 1, 9){cout << a[i][j] << " ";}cout << endl;}*/}}}

该函数对n/2为偶数的情况进行处理。类似于书中的 2 k 2^k 2k的处理方式

具体操作过程是将n一分为2，通过一个正方形中左上角的值来得到其他三个角的值。

右上角的值=左上角值+m，右下角值=左上角值，左下角值=右上角值

以n=2为例：初始仅有一个1，但经过操作后可得到如下结果

1	2
2	1

又如n=4:初始时仅有4个值，但是通过左右两次循环，上下两次循环可以得到如下结果

1	2	1+2=3	2+2=4
2	1	2+2=4	1+2=3
3	4	1	2
4	3	2	1

经过这样是可以解决n/2 为偶数的情况，现在再回到主递归函数，来从n=4生成n=6

void copyodd(int n)
{int m = n / 2;rep(i, 1, m + 1) {b[i] = m + i;b[m + i] = b[i];}rep(i, 1, m + 1){rep(j, 1, m + 2){if (a[i][j] > m){a[i][j] = b[i];a[m + i][j] = (b[i] + m) % n;}elsea[m + i][j] = a[i][j] + m;}rep(j, 2, m + 1){a[i][m + j] = b[i + j - 1];a[b[i + j - 1]][m + j] = i;}}
}

首先我们需要一个循环数组b，他是为了保证我们生成的后两列不会出现重复

比如我们这里的b为 4，5，6，4，5，6 很明显第一行可以取4，5 第二行取5，6 第三行取6，5，这样就正好补齐了前三行的后两列

接着我们通过以现有值叠加m的方式来得到后几行的结果，以第一行的值来确定第四行的值，第二行的值来确定第五行的值，第三行的值来确定第六行的值。

第一次循环：i=1 时，我们依次判断，通过第一个j循环可以得到以下结果