google : Organize football tournament

You need to organize a football tournament. There are n teams given.
You need to prepare a schedule for the matches so that each team plays with every
other team and on the same day no team plays twice. You want to finish the tournament as early as possible.

直观上就是每次尽量分成均匀的两拨，两拨之间互相解决之后就递归解决内部，两边是可以并行的，所以所需要的轮数大约是： T(n) = T(n/2)+n/2  n为偶数， T(n) = T((n+1)/2)+(n+1)/2 n为奇数。只不过要证明这样最优不太容易

直观上就是每次尽量分成均匀的两拨，两拨之间互相解决之后就递归解决内部，两边是可以并行的，所以所需要的轮数大约是： T(n) = T(n/2)+n/2  n为偶数， T(n) = T((n+1)/2)+(n+1)/2 n为奇数。只不过要证明这样最优不太容易
darksteel 发表于 2011-5-24 09:45

没这么复杂吧。n个team,两两都要比赛，可以看作是n个点的无向图。无向图可以用n^2的正方形矩阵表示。由于自己不和自己比赛，对角线除去， 1vs2和2vs1不能重复，所以比赛布局因该是正方形左下角的除去对角线的直角三角形。应为一个队一天不能比赛两次，所以比赛安排因该是：第一天按等腰直角三角形第一个斜边安排，第二天第二条斜边....

回复 3# wwwyhx
这样有问题吧？比如你说第一天第一个斜边，具体分析每个点，分别是(2,1),(3,2),(4,3)。。。每个队都有重复，不能安排到一天啊

回复  wwwyhx
这样有问题吧？比如你说第一天第一个斜边，具体分析每个点，分别是(2,1),(3,2),(4,3)。。。每个队都有重复，不能安排到一天啊
darksteel 发表于 2011-5-28 14:12

    晕，我说的斜边的方向和你理解的不一样，我说的是另外一条
第一天：2,1    2,3    3,4
第二天：1,3    2,4
第三天： 1,4

回复 5# wwwyhx
这第一天，不是还是有重复吗。。。

回复  wwwyhx
这第一天，不是还是有重复吗。。。
darksteel 发表于 2011-5-28 23:19

呵呵，看来弄错了，因该是这样:
选出所有比赛的对数，如果有4个队就是:
(1,2) (1,3) (1,4) (2,3) (2,4) (3,4) 需要安排这6场比赛
用一个bool数组在每个循环里做标记，一个循环代表一天，循环直到所有比赛都完成为止
第一天 ：(1,2) (3,4)
第二天 ：(1,3) (2,4)
第三天 ：(1,4) (2,3)

挺简单的一题怎么被我搞的这么麻烦

回复  wwwyhx
这第一天，不是还是有重复吗。。。
darksteel 发表于 2011-5-28 23:19

呵呵，看来弄错了，因该是这样:
选出所有比赛的对数，如果有4个队就是:
(1,2) (1,3) (1,4) (2,3) (2,4) (3,4) 需要安排这6场比赛
用一个bool数组在每个循环里做标记，一个循环代表一天，循环直到所有比赛都完成为止
第一天 ：(1,2) (3,4)
第二天 ：(1,3) (2,4)
第三天 ：(1,4) (2,3)

挺简单的一题怎么被我搞的这么麻烦

wwwyhx 发表于 2011-5-29 18:51
呵呵，看来弄错了，因该是这样:
选出所有比赛的对数，如果有4个队就是:
(1,2) (1,3) (1,4) (2,3) (2, ...

这个不够美妙，而且复杂度太大。有一个很简单的方法：把n个team放在一个正n边形的n个点上，假设第一天1和2要比赛，那么在1和2之间连一条直线，于是第一天剩下的比赛对应的直线都必须和1、2之间的直线平行，共[n/2]场，中括号表示向下取整，不管n的奇偶（若为奇数则有一队第一天不用比）。第二天2和3比，第三天3和4比，一共比n天搞定。