admin 管理员组

文章数量: 887007

循环赛之分治策略

师说要用分治思想解决，在网上找了都讲解的不是很明白，比赛对数为奇数时，有点费解。不过最后还是想明白了，顺便把作业放这，有兴趣了解的可以看一下，逃）

问题：

有N个运动员进行单循环赛，即每个运动员要和所有其他运动员进行一次比赛。
1．试用分治法为N个运动员安排比赛日程。
2．要求每个（或队）运动员每天只能进行一场比赛，且当运动员人数(队数)为偶数时，整个比赛在N-1天内结束，为奇数时，在N天内结束；
3．将运动员从1到N编号。

思路：
我们用表格的方式来表示循环赛的日程安排，最左边的一列表示队号，每一行表示相应队比赛每天的对手，即a[i][j]表示第i队第j天的对手。
我们从两个队的比赛开始，并发现其中规律：


其中，四队的表格可以从两队的表格产生的：

但这只能解决2的幂的队数的循环赛日程。

为了解决更普遍的队数，我们考虑队数为偶数时，它必然可以被2整除，商为偶数或奇数。商为偶数可以用上面的方法得到结果，商为奇数时，就不行了。
我们先来看一个例子，队数为6时，它的一半为3，是奇数，不能用上面的方法，我们先考虑它的子问题：队数为4时，就是上面求出的结果了，我们要从队数4产生6的结果：

我们可以看到后3行其实和前3行是一样的，只是编号变了而已。为了让编号在6以内，我们要改变编号7的对应情况，可以看出编号7是由编号4产生的，所以我们只要让它们相对的队组成一队

本文标签： 循环赛之分治策略

版权声明：本文标题：循环赛之分治策略 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732355245h1534246.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。