循环赛最短赛程问题

设计一个单循坏赛程表,每位选手每天最多比赛 1 场,还要使比赛在尽可能短的时间内结束。这也许是程序设计课程的经典题目了。不同的是,本文希望探讨人数不是 2 的整数次幂的情形。

要求是,设计一个单循坏赛程表,每位选手每天最多比赛 1 场,还要使比赛在尽可能短的时间内结束。

一种易于写成递归算法的想法是这样。

【方案一】

  • 假如我们已经安排好了 n 个人的单循环赛程表,用时 d 天。
  • 那么,对于 2n 人,我们可以这样安排:
    • 将这 2n 人分成两组,每组 n 人。为便于叙述,记为 甲组 和 乙组。
    • 在前 d 天,让每组的 n 个人分别进行单循环(这将是递归调用);
    • 之后花 n 天,完成所有“一个选手来自甲组,一个选手来自乙组”的比赛。
      • 比如说,这 n 天中第 1 天,甲组1号 vs 乙组1号,甲组2号 vs 乙组2号,直到甲组n号 vs 乙组n号;
      • 第 2 天,把每个乙组选手的编号加1,安排甲组1号 vs 乙组2号,甲组2号 vs 乙组3号,直到甲组(n-1)号 vs 乙组n号,甲组n号 vs 乙组1号;
      • 这样下去第 n 天,安排 甲组1号 vs 乙组n号,甲组2号 vs 乙组1号,直到甲组(n-1)号 vs 乙组(n-2)号,甲组n号 vs 乙组(n-1)号。

可以验证,以上的方案安排比赛,可以做到不重不漏。当 n = 2 时显然有 d = 1,继而可以用数学归纳法证明,

当比赛人数 n 是 2 的幂次(比如 4, 8, 256, 2048, 65536)时,以上方法可以让比赛用时 (n-1) 天结束。

下面来证明该方案是用时最短的方案——根据单循环“每两个选手都比赛一次”的要求,n 人的单循环要比赛 n(n-1)/2 场,而根据“每位选手每天最多比赛 1 场”的要求, (n-1) 天最多只能进行 n(n-1)/2 场比赛。所以赛程不可能比 (n-1) 天更短了。

分治递归,该方案容易编程实现。附 C 语言的代码。

以上方案有个明显的缺陷——只能处理比赛人数 n 是 2 的幂次的情况。如果比赛人数是 33,如果还想用这个方案的话,我们将只能“虚拟”出第 34 到 64 号选手来,然后按 64 个选手来安排。赛程将是 63 天。当然其中有大量的比赛是实际不存在的。有虚拟选手参加的比赛直接从赛程表上抹掉就可以了,不必担心真选手或者裁判员被虚拟选手“放鸽子”自不必担心。我心疼的是,轮空太多了,赛程中的时间将被白白浪费掉。

下面我们希望解决的问题是,对于比赛人数是 33 人这种情况,我们是否可以设计出更短的赛程?

对于人数是奇数的情况,我们首先可以给出日程长度的下限:n,因为要比赛 n(n-1)/2 场,而每天最多只能进行 (n-1)/2 场比赛。对于人数是偶数的情况,同样方法给出的下限是 (n-1)。

下面是资料给出的,人数是偶数时,(n-1) 天搞定的排法:

【方案二】

来源:http://www.docin.com/p-430759465.html

容易验证该方案满足要求。而对于人数是奇数的情况,我们可以虚拟出 1 个选手,应用以上方案,就可以得到一个 n 天的赛程了。

至此我们构造性地证明了以下定理:

若选手数是偶数,单循环赛轮数的最小值是 (n-1) ;若是奇数,最小值是 n 。

(完)

发表评论

电子邮件地址不会被公开。 必填项已用*标注