循环赛日程表问题（分治算法）
设有n=2kn=2^kn=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他n−1n-1n−1个选手各赛一次；
(2)每个选手一天只能参赛一次；
(3)循环赛在n−1n-1n−1天内结束
按此要求将比赛日程表设计成有nnn行和n−1n-1n−1列的一个表。在表中的第iii行，第jjj列处填入第iii个选手在第jjj天所遇到的选手。
题图来自：/weixin_44469806/article/details/108936037
观察上图，可以得出如下交换规律图，斜对角位置交换，规律如下：
#include <stdio.h>int ** getArray(int n){int ** array = new int * [n];for (int i = 0; i < n; i++){array[i] = new int[n]{0};}return array;}void printTable(int ** table, int row, int col){for (int i = 0; i < row; i++){for (int j = 0; j < col; j++){printf("%d ", table[i][j]);}printf("\n");}printf("\n");}int ** splitTableByBound(int ** schedule, int rowstart, int rowend, int colstart, int colend){int blocksize = rowend - rowstart + 1;int ** blocktab = getArray(blocksize);for (int i = 0; i < blocksize; i++){for (int j = 0; j < blocksize; j++){blocktab[i][j] = schedule[rowstart + i][colstart + j];}}return blocktab;}void setTableByBound(int ** table, int ** block, int rowstart, int rowend, int colstart, int colend){for (int i = rowstart; i <= rowend; i++){for (int j = colstart; j <= colend; j++){table[i][j] = block[i - rowstart][j - colstart];}}}int ** mergeTable(int ** fir, int ** sec, int ** thr, int ** fou, int n){int halfsize = n / 2;int ** mergeBlock = getArray(n);setTableByBound(mergeBlock, fir, 0, halfsize - 1, 0, halfsize - 1);setTableByBound(mergeBlock, sec, 0, halfsize - 1, halfsize, n - 1);setTableByBound(mergeBlock, thr, halfsize, n - 1, 0, halfsize - 1);setTableByBound(mergeBlock, fou, halfsize, n - 1, halfsize, n - 1);return mergeBlock;}int ** roundRobTable(int ** schedule, int n){if (n == 1)return schedule;int halfsize = n / 2;int ** firtab = roundRobTable(splitTableByBound(schedule, 0, halfsize - 1, 0, halfsize - 1), halfsize);int ** sectab = roundRobTable(splitTableByBound(schedule, 0, halfsize - 1, halfsize, n - 1), halfsize);int ** thrtab = roundRobTable(splitTableByBound(schedule, halfsize, n - 1, 0, halfsize - 1), halfsize);int ** foutab = roundRobTable(splitTableByBound(schedule, halfsize, n - 1, halfsize, n - 1), halfsize);return mergeTable(firtab, sectab, sectab, firtab, n);}int main(){int * initvalue = new int[8]{1, 2, 3, 4, 5, 6, 7, 8};int ** initschedule = getArray(8);initschedule[0] = initvalue;printTable(initschedule, 8, 8);int ** schedule = roundRobTable(initschedule, 8);printTable(schedule, 8, 8);return 0;}
如果觉得《循环赛日程表问题（分治算法）》对你有帮助，请点赞、收藏，并留下你的观点哦！
