网球循环赛日程表..docx

问题表述： 设有n个运动员要进行网球循环赛。设计一个满足以下要 求的比赛日程表， (1) 每个选手必须与其他n-1个选手各赛一次； (2) 每个选手一天只能赛一次； (3) 当n是偶数时，循环赛进行n-1天，当n是奇数时，循环 赛进行n天 分析问题 题目是要n名运动员进行循环比赛。当n为偶数时，正好每天都可以两两一组，与其余的n-1个选手比赛，只需n-1天； 而当n为奇数，每天将有一个选手轮空，比赛将持续n天。 可以采用的算法如下： 算法一：使用分治法 当n为偶数时，可以讲问题分为两个部分n/2; 然后继续划分，知道最后剩余两名选手单独比赛。当n为奇数时，增设一个虚拟选手，运动员为n+1个，将问题转化为是偶数的情形。当选手与虚拟选手比赛时，表示轮空，因此只需要关注n为偶数的情形。 当n/2为偶数时，与n = 2^k情形类此。 当n/2为奇数时，增设一个虚拟的选手，递归返回的将有轮空的选手，可以讲在前面n/2轮比赛的选手与后面n/2轮空的选手进行比赛。 算法二：利用边是奇数的正多边形。 特点：以多边形中的任意一个顶点画对称轴，其余偶数对顶点相互对称。 N名选手编号为1~n，将其画成一个正多边形。 所以当n为奇数时，第一天1号休息，其余以一号为对称轴，两两对称打比赛，第二天开始一次轮流休息，其余一休息的那个人编号为对称轴，两两比赛。这样比赛可进行n天。如图： 此时n=9，为奇数，从0开始每天有一个人轮空 此时n=9，为奇数，从0开始每天有一个人轮空 对称轴 对称轴 对称轴 当n为偶数时，取出编号最大的，其他的组成一个正多边形，n号一次顺序与1,2，。。。n-1号选手比赛，其他与a）相同。如图所示：（图中是从0开始编号） 99 9 9 N=2k时 N=2k时 9 9 理论分析算法及实现 算法一：使用分治法 算法的思路：按分治策略，可以将所有的选手对分为两组（如果n是偶数，则直接分为n/2每组，如果n是奇数，则取（n+1）/2每组），n个选手的比赛日程表就可以通过为（n/2或（n+1）/2）个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。下图给出的是六个选手的比赛日程表，其中第一列表示1-6个选手，第二列到第六列表示各个选手在第一天到第五天的所遇到的选手。1 2 3 4 5 62 1 5 3 6 43 6 1 2 4 54 5 6 1 3 25 4 2 6 1 36 3 4 5 2 1在这里算法设计的难点就是分开治理后的合并问题。这里我就结合上面给出的6个选手的示例来进行表述。首先，将6个选手分为对等的两组，每组3个选手。每组增设一个虚拟的选手，然后再递归的将3个选手分为对等两组，每组2个选手。在2个选手情况下，这两个选手比赛。可以得到两个选手的日程安排表是：1 22 1接下来的任务是合并这两组2个选手的日程表得到3个选手的日程安排表，这里我先假设有4个选手参加比赛则：1 22 13 44 3接下来的比赛里，第二天让1和3比赛，2和4比赛；第三天让1和4比赛，2和3比赛，即让前一组的选手，循环的和后一组的选手比赛，可得到比赛日程安排表是：1 2 3 42 1 4 33 4 1 24 3 2 1这里要得到的是3个选手的日程安排表，则第4个选手是假想的选手将其用0来表示则得到3个选手的日程安排表：1 2 3 02 1 0 33 0 1 2接下来的任务是合并这两个3个选手的日程安排表得到6个选手的日程安排表，这里我们的两组选手前3天的比赛情况如下：1 2 3 02 1 0 33 0 1 24 5 6 05 4 0 66 0 4 5其中第一天选手3和选手6都没有对手，让他们两个比赛；第二天选手2和选手5没有对手，让他们两个比赛，；第三天选手1和选手4没有对手，让他们两个比赛。这就可以得到合并后6个选手前三天的比赛日程安排表：1 2 3 42 1 5 33 6 1 24 5 6 15 4 2 66 3 4 5将在前三天比过赛的两组的选手对应的列出来：1 2 34 5 6在这里可以看到合并的两组中3和6，2和5，1和4都已经比过了，这里就跳过这些选手的比赛，然后两个组循环比赛即：1 2 35 6 4和1 2 36 4 5这样就得到了6个选手的比赛完整的日程安排表：1 2 3 4 5 62 1 5 3 6 43 6 1 2 4 54 5 6 1 3 25 4 2 6 1 36 3 4 5 2 1 证明算法的正确性：（1） 在n=2时，就这两个选手比赛，比赛只进行一天，这也是算法的初始情况，算法成立。（2）