算法课的作业，问题如下：
和书上的问题有所不同，书上人数只能是2^k人，而作业中的题目要求为n人。书上的分治法很好理解，矩阵左上移到右下，左下移到右上就可以解决问题，但扩展到奇数人时就不适用了，查询网上的代码也很难理解，在查询资料过程中看到了一篇研究该问题的论文，是采用找规律的方法，不含任何算法上的技巧，比较朴实无华，但是我觉得很有意思，就按照他的思路自己编写了代码完成此次作业。具体如下思路：
假设有N名选手参赛，我们首先构造一个N×N的矩阵。在矩阵第一行填充1，2,…,N，第一列填充1，2,…,N。这样做的意义取决于我们对这个矩阵的定义。我把矩阵的第一列作为参赛选手的编号，第2~N列作为某一参赛选手的对手，显然任意的人数的选手其第一行都是一行选手，对手为2，3,…,N号选手，第一列是所有选手编号1，2，…,N。但是以上我们的构造存在一个问题，就是这种假设默认了参赛选手人数是偶数，因为只有人数是偶数的情况下才只会需要N-1天（N-1列参赛选手）就完成比赛。所以我们不妨先考虑是选手是偶数的情况。
在构造了以上矩阵后，我们先观察一下最终答案的矩阵：
可以发现以下规律：
1.对角线上的元素全部为1。
2.考虑所有与对角线平行的斜线，对于上半矩阵，将对角线作为第一条斜线，之后的第2,3,…,N-1条斜线上的取值全部依次为2,3,…,N-1。如果斜线中的某一行原本的要取的值与所在行数相同，则取最大值N（如图1，第二行第三列位于第二条斜线，原本要取2，当因为他也在第二行，故取最大值6）。对于下半矩阵，规律也是类似的，将对角线作为第一条斜线，之后的第2,3,…,N-1条斜线取值依次为N-1,N-2,N-3……。同样的如果要取的值与行数相同则取最大值N。
3.上述规律仅对N-1行适用，即通过上述规律得到的结果中第N行是错误的结果。
通过以上规律我们的思路就非常明确了，在N是偶数的情况下，进行以下操作：
1.按照上述规律对上半矩阵赋值。
2.对下半矩阵赋值。
3.对于得到矩阵，由于其每一列的和必定为sum=1+2+⋯+N，故用sum减去前N-1列的值，得到该列最后一行的值。
具体代码如下：
if(N % 2 == 0){
// 上半区对角线方向赋值
for (i = 2; i <= N; i ++){
for (j = 1; j <= N; j ++){
if (j + 1 == i) {// 如果要赋的值与所在行数相同
a[i][i+j] = N;// 赋予最大值
continue;
}
a[i][i+j] = j + 1;
}
}
// 下半区对角线方向赋值
for (i = 3; i <= N; i ++){
for (j = i - 1, k = N - 1; j > 1; j --){
if (k == i){
a[i][j] = N;
k --;
continue;
}
a[i][j] = k --;
}
}
int sum = 0, ss = 0;
for(i = 1; i <= N; i ++){
sum += i;
}
for (i = 2; i <= N; i ++) {
for (j = 1; j <= N - 1; j ++){
ss += a[j][i];
}
a[j][i] = sum - ss;
ss = 0;
}
}
接下来我们接着考虑奇数的情况：
首先还是观察一下最终答案的矩阵：
规律似乎有点难找，那么再观察下面两个矩阵呢？
很容易发现，对于奇数情况，我们可以先为他添加1使其变为偶数人的情况，不同的是，当斜线上存在相同值时我们不是添加最大值，而是添加0（0表示轮空）。得到的结果矩阵删去最后一行就是我们所需要的结果了。所以对于偶数情况，我们的代码要改的地方就是将传入的N+1，然后相同值由添加N改为添加0即可。此外，由于删去了最后一行，我们不需要再考虑偶数时最后一行得到的值不正确的情况了，故不需要再对每一列求和。
具体代码如下：
else{
flag = false;
N += 1;
for (i = 2; i <= N; i ++){
for (j = 1; j <= N; j ++){
if (j + 1 == i) {// 如果要赋的值与所在行数相同
a[i][i+j] = 0;// 赋予0
continue;
}
a[i][i+j] = j + 1;
}
}
// 下半区对角线方向赋值
for (i = 3; i <= N; i ++){
for (j = i - 1, k = N - 1; j > 1; j --){
if (k == i){
a[i][j] = 0;
k --;
continue;
}
a[i][j] = k --;
}
}
}
至此便完美的解决了问题。
完整代码：
#include
using namespace std;
int a[101][101] = {0};
int main(int argc, const char * argv[]) {
// insert code here...
int N, i, j, k;
cout << "请输入参赛人数：";
cin >> N; // 比赛人数
for (i = 1; i <= N; i ++){
a[1][i] = a[i][1] = i;
a[i][i] = 1;
}
bool flag = true; // N为偶数
// 偶数人
if(N % 2 == 0){
// 上半区对角线方向赋值
for (i = 2; i <= N; i ++){
for (j = 1; j <= N; j ++){
if (j + 1 == i) {// 如果要赋的值与所在行数相同
a[i][i+j] = N;// 赋予最大值
continue;
}
a[i][i+j] = j + 1;
}
}
// 下半区对角线方向赋值
for (i = 3; i <= N; i ++){
for (j = i - 1, k = N - 1; j > 1; j --){
if (k == i){
a[i][j] = N;
k --;
continue;
}
a[i][j] = k --;
}
}
int sum = 0, ss = 0;
for(i = 1; i <= N; i ++){
sum += i;
}
for (i = 2; i <= N; i ++) {
for (j = 1; j <= N - 1; j ++){
ss += a[j][i];
}
a[j][i] = sum - ss;
ss = 0;
}
}
// 奇数人
else{
flag = false;
N += 1;
for (i = 2; i <= N; i ++){
for (j = 1; j <= N; j ++){
if (j + 1 == i) {// 如果要赋的值与所在行数相同
a[i][i+j] = 0;// 赋予0
continue;
}
a[i][i+j] = j + 1;
}
}
// 下半区对角线方向赋值
for (i = 3; i <= N; i ++){
for (j = i - 1, k = N - 1; j > 1; j --){
if (k == i){
a[i][j] = 0;
k --;
continue;
}
a[i][j] = k --;
}
}
}
if(flag){
for (i = 1; i <= N; i ++) {
for (j = 1; j <= N; j ++){
cout << a[i][j] << "\t";
if (j == 1){
cout << "|\t";
}
}
cout << endl;
}
}
else{
for (i = 1; i <= N - 1; i ++) {
for (j = 1; j <= N; j ++){
cout << a[i][j] << "\t";
if (j == 1){
cout << "|\t";
}
}
cout << endl;
}
}
return 0;
}
运行结果：
参考文献
[1]刘超. 扩展循环赛日程表算法研究[J].辽宁工程大学学报,2004,(23):50-52.
[2]王晓东.计算机算法设计与分析[M].北京:电子工业出版社,2001.