单循环赛赛程安排算法研究

单循环赛赛程安排算法研究 单循环赛赛程安排算法研究,开发研究与技术, 章林忠 约2699字 摘要:循环赛赛程安排算法是一个很经典的计算机算法，它是分治法的一个经典应用， 但该算法只适应于2n支队伍的赛程安排问，而对于非 2n支队伍的赛程安排问题却没有很 好的解决。文章使用可视化语言Visual Basic作为开发工具，借助于循环队列的规律，针对 任意n支队伍的赛程安排提出一种直观、方便的算法。 关键词:单循环赛;赛程安排;算法;Visual Basic 6.0 中图分类号:TP312文献标识码:A文章编号:1009-3044(2007)15-30805-02 Single Cycle Match Competition Schedule Arrangement Algorithm Research ZHANG Lin-zhong (Anhui Agricultural University,College of Applied Mathematics Institute,Hefei 230036) Abstract:Round robin schedule algorithm is a classic computer algorithm,it is a representative application of the divide and rule algorithm, but the classical computer algorithm can solve match arrangement of 2n teams only, it can not satisfactorily resolve the problem of not 2n teams. The article using Visual Basic as a development tool, using cohort cycle of the law against arbitrary n teams in the schedule proposed an intuitive and user-friendly algorithm. Key words:Single round robin;the schedule;Algorithm;Visual Basic 6.0 1 引言 在计算机算法中，循环赛赛程安排算法是是分治法的一个经典应用，但该算法只适应于 2n支队伍的赛程安排问题，而对于任意n支队伍的赛程安排问题却不能很好的解决。文献4 中对该算法作了一个补充，可以对任意支队伍进行比赛的赛程进行安排，但该算法不是很直 观，而且通过Turbo C实现，操作起来不是很方便。本文采用面向对象的开发工具Visual Basic， 提出一种更为简单的算法，得到更为直观、操作方便的结果。 2 单循环赛赛程算法 单循环赛，是所有参加比赛的队伍均能相遇一次，最后按各队在全部比赛中的积分、得 失分率排列名次。这种竞赛方法满足(假设有n支队伍):a、每支队伍必须与其他n-1支队 伍各赛一次;b、每支队伍每轮只能进行一场比赛。很明显，当 n为奇数时，需进行n轮比 赛;当 n为偶数时，需进行n-1轮比赛。首先考虑n为奇数的情况，在此基础上再考虑n为 偶数时的情况。 (1)当比参赛队(或人)为奇数即n=2*k-1 (n?2)时，考虑到每轮均有一支队伍轮空， 先将队伍一分为二，每轮比赛在前后两部分中依次选取一支队伍进行比赛，第一轮将k号选 手轮空，利用对称性，将1号队伍和n号队伍比赛，2号队伍和n-1号队伍比赛，依此类推 排完第一轮选手的比赛;第二轮将k+1号队伍轮空，再将2号队伍和1号队伍比赛，3号队 伍和n号队伍比赛，依此类推排完第二轮选手的比赛;为了避免两个队之间出现重复比赛， 所以用循环队列(如图1)的方式解决每轮轮空队伍的编号，即编号为n的队伍轮空的下一 轮为编号1的队伍轮空。例:7支队伍参加比赛的排法(见图2): 图1 循环队列 第一轮 1-7 2-6 3-5 第二轮 2-1 3-7 4-6 第三轮 3-2 4-1 5-7 第四轮 4-3 5-2 6-1 第五轮 5-4 6-3 7-2 第六轮 6-5 7-4 1-3 第七轮 7-6 1-5 2-4 图2 7支队伍 (2)当比赛队伍数为偶数即n = 2*k(n?2)时，每一轮比赛只需在n=2*k(n?2)的基础上 补上轮空的队伍和编号为n的队伍比赛即可。例:8支队伍参加比赛的排法(见图3): 第一轮 1-7 2-6 3-5 4-8 第二轮 2-1 3-7 4-6 5-8 第三轮 3-2 4-1 5-7 6-8 第四轮 4-3 5-2 6-1 7-8 第五轮 5-4 6-3 7-2 1-8 第六轮 6-5 7-4 1-3 2-8 第七轮 7-6 1-5 2-4 3-8 图3 8支队伍 3 算法实现 本算法采用VB语言来实现，在编程时用两个了变量a，b(a示奇数列选手编号，b表 示偶数列选手编号)，并用两个循环分别控制a和b的变化。由于a和b是循环变化的，为防 止数据溢出，所以在编程时分别用了判断语句来判断，若新增的a和b大于n，便取他们除 以n的余数，否则就取他们本身。当n为奇数时的相应程序如下: If n Mod 2=1 Then For i=1 To n a=i If n+i- 1>n Then b=(n+i-1) Mod n Else b=i+n-1 End If For j=1 To (n-1)/2 If a+1>n Then a=(a+1) Mod n Else a=a+1 End If If b+n-1>n Then b=(b+n-1) Mod n Else b=b+n-1 End If Next j Next i End If 当n为偶数时，程序和奇数的时候基本差不多，这里就不再重复了。该算法的时间复杂 度为0(n2),与文献4中提到的算法的时间复杂度相同，但结果更为直观，操作更为方便，其 运行结果如图4(n=13)和图5(n=10)所示: 图4 参赛队伍人数为奇数(n=13)时运行结果 4 结束语 单循环赛赛程安排的算法很多，分治法对任意n支队伍的情况不能解决，扩展循环赛日程表算法是分治法的一个补充，解决了任意n支队伍的情况，但不是很通俗易懂，而且用C语言实现的算法不够直观。本文提出一种更为简单的算法，并且利用可视化语言Visual Basic进行开发，此软件具有界面友好、操作方便、运行可靠的特点，使用起来方便快捷。 图5 参赛队伍人数为偶数(n=10)时运行结果 参考文献: [1]王晓东.计算机算法设计与分析[M].电子工业出版社,2001年1月. [2]龚沛曾,陆慰民,杨志强.Visual Basic程序设计简明教程(第2版)[M].高等教育出版社,2003年3月. [3]严蔚敏,吴伟民,数据结构(C语言版)[M].清华大学出版,1997年4月. [4]刘超,刘建辉,林森,扩展循环赛日程表算法研究[J].辽宁:辽宁工程技术大学学报,第23卷增刊2004年6月,50-52. 注:本文中所涉及到的图表、注解、公式等请以PDF格式阅读原文。