求排赛程表的算法
比如有1,2,3,4,5,6,7,8支球队要打单循环联赛,怎么安排他们的赛程啊?
我自己写了一个算法,但只支持2的n次方支球队。看样子好像要用分治法,但具体怎么分有哪个大虾可以说说吗?
这么经典的一个算法为什么CSDN对它的讨论这么少啊,晕~~
[解决办法]
如果,n是奇数的话,先设一只队伍n+1,每轮和这个虚设的队伍比赛的队伍就是轮
空,所以,我们下面假设n为偶数,
然后,设n个队伍编号分别是1,2,3,...,n,
在第k(1<=k<=n-1)轮,如果1<=i,j<=n-1, i<>j, (i+j-k)%(n-1)=0的,则第i队和
第j队比赛,第n队与由方程(2*x-k)%(n-1)=0决定的队伍x比赛。
可以证明,这样可以得到排法符合单循环规则。
举个例子,有5个队伍
第1轮 1-5 2-4 3-x
第2轮 1-x 2-5 3-4
第3轮 1-2 3-5 4-x
第4轮 1-3 2-x 4-5
第5轮 1-4 2-3 5-x
x是虚设队,就是碰上表示轮空