发布时间 : 星期五 文章循环赛日程表更新完毕开始阅读b50c9743767f5acfa1c7cd2d
算法设计与分析实验报告
循环赛日程表
一． 问题描述
设有n位选手参加循环赛，设计循环赛日程表，要求： 每位选手必须和其余n-1个选手比赛； 每位选手每天只能比一场比赛；
若n为奇数，则比赛n天； 若n为偶数，则比赛n-1天。
二． 实验目的
熟悉分治法的思想并掌握其运用。 三． 实现方式
编译环境：Dev-C++ 算法思路：
使用分治法的思想，给n个选手安排日程表转化为给n/2个选手安排日程表，直到问题规模变成给两个选手安排日程。 日程表可以用一个二维数组表示，数组的大小为k（n<=2^k），第i行第j列的数组值表示第i个选手在第j-1天比赛的对手（第1列表示选手的编号，假定选手的编号为1，2，3…恰为数组的行数）。
划分：n个选手的日程表可以由n/2个选手的日程表合并而得。
解决：当只有两个选手比赛的时候，可以直接给出其日程表，得到一个2×2的数组。
当有4个选手参加比赛的时候，则将两个2×2的数组合并，得到一个4×4的数组。
1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 以此类推，n个选手的日程表由n-1个选手的日程表合并而成。合并规则为：
若n为偶数，则会得到一个n×n的表格；若n为奇数，需要比赛n天，则会得到一个n×（n+1）的表格且每一天必定有一位选手轮空。因此在合并的时候要先把表格扩充为（n+1）×（n+1）的表格，然后再消除虚拟的选手（用0表示轮空）。
例：n=3时赛程表为：
1 2 3 0 2 1 0 3 3 0 1 2 当n=6时，将两个n=3的赛程表合并，在同一天轮空的选手便可
在该天比赛。然后再补上表格右边的元素。 1 2 3 4 2 3 4 5 6 1 6 5 4 3 5 1 6 2 4 3 2 1 6 5 设当前要合并的数组的长度为s，表格左下角的元素可由左上角的元素+s而得：
表格右上角的元素由前一行决定：
表格右下角的元素由表格右上角对应元素所决定：