淘汰赛编排中根种子算法

董东风   
（长沙通信职业技术学院  湖南  长沙  邮编  ４１００１５）

摘  要：在体育竞赛淘汰赛的编排中，运用传统理论，虽然能解决实际编排问题，但不能解决给定２ｎ个位置，来排定２ｎ个有序种子号码和（２ｎ—Ｎ）个空位的位置问题。本文作者采用列举推导法，通过手工对种子号码排位，推导出了在淘汰赛编排中对种子队排位的算法，从而解决了计算机替代手工编排的算法问题。
关键词：种子；位置；算法
   
    随着信息社会的到来，体育竞赛信息化的建设势在必行，其中包括竞赛编排信息化的建设。然而，传统竞赛编排的方法和原理理论，在某些方面已不能满足现代体育竞赛信息化建设的需要。这在很大程度上是因为，对竞赛编排方法和原理的研究只考虑到了手工能处理的水平上，而没有考虑到信息化处理对其算法提出的要求。因而，阻碍了体育竞赛信息化建设的进程。
    在给定参赛队数和种子队数的条件下，编排出淘汰赛轮次表中的空位和种子位，这是淘汰赛编排中需要解决的问题。运用传统理论，虽然能解决实际编排问题，但不能解决给定２ｎ个位置，来排定２ｎ个有序种子号码和（２ｎ—Ｎ）个空位的位置问题。
    我们知道，在淘汰赛编排中，把强队按已往成绩设为相应种子队，依据“上区顶部、下区底部、下区顶部、上区底部”顺序的原则把种子队分散排在淘汰赛轮次表的各个区上，从而避免强队过早相遇，这就是学术上所说的根种子原理。实际上这个理论是个很抽象的概念，在实际运用中不可能规范化。
    另外，根据参赛队数的多少，淘汰表的位置数有唯一的确定，其关系表达式是２ｎ≥Ｎ（Ｎ为参赛队数；ｎ为大于１的正整数）。也就是说，淘汰表中的位置数是按２的幂次方增加的，如果参赛队数不是２的幂次方，那么，淘汰表中就会出现（２ｎ—Ｎ）个空位置。如何设置空位置，学术上对这个问题早有研究，提出了用轮空位置表（见表１）来解决空位置的设置问题。目的是除第一轮比赛外，以后各轮比赛不再出现轮空队。例如，１３个队的淘汰赛，位置数是１６，空位置数是３。３个空位置从表中依次从左至右找出３个小于１６的数，那么２、１５、１０就是空号码位置，与２、１５、１０空号相遇的队便为轮空队；然而，这个表存在着一定的局限性。从表中也可以看出，只有８个位置号码，显然不能解决有ｎ个参赛队时的轮空位置的设置问题。有趣的是，在表２中，２５的下半区最后８个位置上种子号码与表１中的数据是一样的，从这也可以看出表１是不全面的。 
[SITESERVER_PAGE]    要解决上述问题，关键是要知道种子号码在淘汰表中的排位规律。我们知道。在篮球循环赛的编排中，编排种子队的位置是按位置号码的顺序排定的，即种子号码与位罩号码是从小到大一一对应的。但在淘汰表中，种子号码与位置号码的对应关系却不是这样简单。   
    我们用手工给种子号码排位，设种子数与位置数相等，先从两个位置开始排，１号位置排１号种子，２号位置排２号种子，我们把这两个种子称之为根种子。然后，按２ｋ（ｋ＝２，３，４…ｎ）增加位置数和种子数，依据根种子原理把种子号码依次排放到给定２ｋ个位置的淘汰表上。这样，我们就可以得到表２。
    我们先把表２中的位置号码进行分区，在给定２ｋ个位置时，全区表示１至２ｋ个位置；上半区表示１至（２ｋ/２）个位置；下半区表示（２ｋ/２）＋１至２ｋ个位置。然后，分别把２ｋ个位置的全区与２ｋ＋１个位置的上半区进行比较，把２ｋ＋１个位置的上半区与２ｋ＋１个位置的下半区进行比较。这样，我们就可以从中发现种子号码在淘汰表中的排位规律。
    ２１的全区与２２的上半区奇偶对应；２２的上半区与２２的下半区奇偶对应；２２的全区与２３的半区奇偶对应；２３的上半区与２３的下半区奇偶对应。依此类推。２ｋ的全区与２ｋ＋１的上半区奇偶对应；２ｋ＋１的上半区与２ｋ＋１的下半区奇偶对应。其对应关系的表达式是：   
    ２１的全区奇数位置上的种子号码乘２减１就等于２２的上半区奇数位置上的种子号码；２１的全区偶数位置上的种子号码乘２就等于２２的上半区偶数位置上的种子号码。
    ２２的上半区奇数位置上的种子号码加２就等于２２的下半区奇数位置上的种子号码；２２的上半区偶数位置上的种子号码减２就等于２２的下半区偶数位置上的种子号码。
    ２２的全区奇数位置上的种子号码乘２减１就等于２３的上半区奇数位置上的种子号码；２２的全区偶数位置上的种子号码乘２就等于２３的上半区偶数位置上的种子号码。
    ２３的上半区奇数位置上的种子号码加２就等于２３的下半区奇数位置上的种子号码；２３的上半区偶数位置上的种子号码减２就等于２３的下半区偶数位置上的种子号码。依此类推。
    ２ｋ的全区奇数位置上的种子号码乘２减１就等于２ｋ＋１的上半区奇数位置上的种子号码。２ｋ的全区偶数位置上的种子号码乘２就等于２ｋ＋１的上半区偶数位置上的种子号码。
    ２ｋ＋１的上半区奇数位置上的种子号码加２就等于２ｋ＋１的下半区奇数位置上的种子号码；２ｋ＋１的上半区偶数位置上的种子号码减２就等于２ｋ＋１的下半区偶数位置上的种子号码。
[SITESERVER_PAGE]    要注意的是，表２中的种子号码数据是我们用手工推算出来的，实际上表２中除根种子号码是我们设定的外，其余都是未知的。因此，在实际运用中，我们每次都要从根种子开始计算。因此，我们称上述算法为根种子算法。有了这个算法就可以编写出根种子排位程序。至于轮空位置的问题，可以把空位置可以看作是大于参赛队数的种子号码，这样，如果某位置上排的种子号码大于参赛队数，那么，就可判别该位置为空位。
程序：根种子排位（程序略）。
输入：（１）参赛队数，（２）种子队数。
输出：（１）位置号码，（２）种子号码，（３）空位标志。
表３，是该程序的一个输出例子。

参考文献：
［１］周贤江编著．篮球运动管理概论［Ｊ］．红旗出版社，１９９９年１２月版。
［２］全国体育院校教材委员会审定：篮球运动教程［Ｍ］．人民体育出版社，２００１年１０月版。