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

1、单循环赛赛程安排算法研究摘要：循环赛赛程安排算法是一个很经典的计算机算法，它是分治法的一个经典应用，但该算法只适应于2n支队伍的赛程安排问题，而对于非2n支队伍的赛程安排问题却没有很好的解决。文章使用可视化语言VisualBasic作为开发工具，借助于循环队列的规律，针对任意n支队伍的赛程安排提由一种直观、方便的算法。关键词：单循环赛；赛程安排；算法；VisualBasic6.0中图分类号：TP312文献标识码：A文章编号：1009-3044(2007)15-30805-02SingleCycleMatchCompetitionScheduleArrangementAlgorithmResea

2、rchZHANGLin-zhong(AnhuiAgriculturalUniversity,CollegeofAppliedMathematicsInstitute,Hefei230036)Abstract:Roundrobinschedulealgorithmisaclassiccomputeralgorithm,itisarepresentativeapplicationofthedivideandrulealgorithm,buttheclassicalcomputeralgorithmcansolvematcharrangementof2nteamsonly,itcannotsatis

3、factorilyresolvetheproblemofnot2nteams.ThearticleusingVisualBasicasadevelopmenttool,usingcohortcycleofthelawagainstarbitrarynteamsinthescheduleproposedanintuitiveanduser-friendlyalgorithm.Keywords:Singleroundrobin;theschedule;Algorithm;VisualBasic6.01引言在计算机算法中，循环赛赛程安排算法是是分治法的一个经典应用，但该算法只适应于2n支队伍的赛程安

4、排问题，而对于任意n支队伍的赛程安排问题却不能很好的解决。文献4中对该算法作了一个补充，可以对任意支队伍进行比赛的赛程进行安排，但该算法不是很直观，而且通过TurboC实现，操作起来不是很方便。本文采用面向对象的开发工具VisualBasic,提由一种更为简单的算法，得到更为直观、操作方便的结果。2单循环赛赛程算法单循环赛，是所有参加比赛的队伍均能相遇一次，最后按各队在全部比赛中的积分、得失分率排列名次。这种竞赛方法满足（假设有n支队伍）：a、每支队伍必须与其他n-1支队伍各赛一次；b、每支队伍每轮只能进行一场比赛。很明显，当n为奇数时，需进行n轮比赛；当n为偶数时，需进行n-1轮比赛。首先考

5、虑n为奇数的情况，在此基础上再考虑n为偶数时的情况。（1）当比参赛队（或人）为奇数即n=2*k-1（nA2）时，考虑到每轮均有一支队伍轮空，先将队伍一分为二，每轮比赛在前后两部分中依次选取一支队伍进行比赛，第一轮将k号选手轮空，利用对称性，将1号队伍和n号队伍比赛，2号队伍和n-1号队伍比赛，依此类推排完第一轮选手的比赛；第二轮将k+1号队伍轮空，再将2号队伍和1号队伍比赛，3号队伍和n号队伍比赛，依此类推排完第二轮选手的比赛；为了避免两个队之间由现重复比赛，所以用循环队列（如图1）的方式解决每轮轮空队伍的编号，即编号为n的队伍轮空的下一轮为编号1的队伍轮空。例：7支队伍参加比赛的排法（见图2

6、）:图1循环队列第一轮1-72-63-5第二轮2-13-74-6第三轮3-24-15-7第四轮4-35-26-1第五轮5-46-37-2第六轮6-57-41-3第七轮7-61-52-4图27支队伍(2)当比赛队伍数为偶数即n=2*k(nA2)时，每一轮比赛只需在n=2*k(nn2)的基础上补上轮空的队伍和编号为n的队伍比赛即可。例：8支队伍参加比赛的排法(见图3):第一轮1-72-63-54-8第二轮2-13-74-65-8第三轮3-24-15-76-8第四轮4-35-26-17-8第五轮5-46-37-21-8第六轮6-57-41-32-8第七轮7-61-52-43-8图38支队伍3算法实现

7、本算法采用VB语言来实现，在编程时用两个了变量a,b(a表示奇数列选手编号，b表示偶数列选手编号)，并用两个循环分别控制a和b的变化。由于a和b是循环变化的，为防止数据溢由，所以在编程时分别用了判断语句来判断，若新增的a和b大于n,便取他们除以n的余数，否则就取他们本身。当n为奇数时的相应程序如下：IfnMod2=1ThenFori=1Tona=iIfn+i-1>nThenb=(n+i-1)ModnElseb=i+n-1EndIfForj=1To(n-1)/2Ifa+1>nThena=(a+1)ModnElsea=a+1EndIfIfb+n-1>nThenb=(b+n-1)M

8、odnElseb=b+n-1EndIfNextjNextiEndIf当n为偶数时，程序和奇数的时候基本差不多，这里就不再重复了。该算法的时间复杂度为0（n2）,与文献4中提到的算法的时间复杂度相同，但结果更为直观，操作更为方便，其运行结果如图4（n=13）和图5（n=10）所示：图4参赛队伍人数为奇数（n=13）时运行结果4结束语单循环赛赛程安排的算法很多，分治法对任意n支队伍的情况不能解决，扩展循环赛日程表算法是分治法的一个补充，解决了任意n支队伍的情况，但不是很通俗易懂，而且用C语言实现的算法不够直观。本文提由一种更为简单的算法，并且利用可视化语言VisualBasic进行开发，此软件具有界面友好、操作方便、运行可靠的特点，使用起来方便快捷。图5参赛队伍人数为偶数（n=10）时运行结果参考文献：1王晓东.计算机算法设计与分析M,电子工业由版社,2001年1月.2龚沛曾，陆慰民杨志强.VisualBasic程序设计简明教程（第2版）M.高等教育由版社，20