單循環(huán)賽賽程安排算法研究

1、單循環(huán)賽賽程安排算法研究摘要：循環(huán)賽賽程安排算法是一個很經典的計算機算法，它是分治法的一個經典應用，但該算法只適應于2n支隊伍的賽程安排問題，而對于非2n支隊伍的賽程安排問題卻沒有很好的解決。文章使用可視化語言VisualBasic作為開發(fā)工具，借助于循環(huán)隊列的規(guī)律，針對任意n支隊伍的賽程安排提由一種直觀、方便的算法。關鍵詞：單循環(huá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引言在計算機算法中，循環(huán)賽賽程安排算法是是分治法的一個經典應用，但該算法只適應于2n支隊伍的賽程安

4、排問題，而對于任意n支隊伍的賽程安排問題卻不能很好的解決。文獻4中對該算法作了一個補充，可以對任意支隊伍進行比賽的賽程進行安排，但該算法不是很直觀，而且通過TurboC實現(xiàn)，操作起來不是很方便。本文采用面向對象的開發(fā)工具VisualBasic,提由一種更為簡單的算法，得到更為直觀、操作方便的結果。2單循環(huán)賽賽程算法單循環(huán)賽，是所有參加比賽的隊伍均能相遇一次，最后按各隊在全部比賽中的積分、得失分率排列名次。這種競賽方法滿足（假設有n支隊伍）：a、每支隊伍必須與其他n-1支隊伍各賽一次；b、每支隊伍每輪只能進行一場比賽。很明顯，當n為奇數(shù)時，需進行n輪比賽；當n為偶數(shù)時，需進行n-1輪比賽。首先考

5、慮n為奇數(shù)的情況，在此基礎上再考慮n為偶數(shù)時的情況。（1）當比參賽隊（或人）為奇數(shù)即n=2*k-1（nA2）時，考慮到每輪均有一支隊伍輪空，先將隊伍一分為二，每輪比賽在前后兩部分中依次選取一支隊伍進行比賽，第一輪將k號選手輪空，利用對稱性，將1號隊伍和n號隊伍比賽，2號隊伍和n-1號隊伍比賽，依此類推排完第一輪選手的比賽；第二輪將k+1號隊伍輪空，再將2號隊伍和1號隊伍比賽，3號隊伍和n號隊伍比賽，依此類推排完第二輪選手的比賽；為了避免兩個隊之間由現(xiàn)重復比賽，所以用循環(huán)隊列（如圖1）的方式解決每輪輪空隊伍的編號，即編號為n的隊伍輪空的下一輪為編號1的隊伍輪空。例：7支隊伍參加比賽的排法（見圖2

6、）:圖1循環(huán)隊列第一輪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)當比賽隊伍數(shù)為偶數(shù)即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算法實現(xiàn)

7、本算法采用VB語言來實現(xiàn)，在編程時用兩個了變量a,b(a表示奇數(shù)列選手編號，b表示偶數(shù)列選手編號)，并用兩個循環(huán)分別控制a和b的變化。由于a和b是循環(huán)變化的，為防止數(shù)據(jù)溢由，所以在編程時分別用了判斷語句來判斷，若新增的a和b大于n,便取他們除以n的余數(shù)，否則就取他們本身。當n為奇數(shù)時的相應程序如下：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為偶數(shù)時，程序和奇數(shù)的時候基本差不多，這里就不再重復了。該算法的時間復雜度為0（n2）,與文獻4中提到的算法的時間復雜度相同，但結果更為直觀，操作更為方便，其運行結果如圖4（n=13）和圖5（n=10）所示：圖4參賽隊伍人數(shù)為奇數(shù)（n=13）時運行結果4結束語單循環(huán)賽賽程安排的算法很多，分治法對任意n支隊伍的情況不能解決，擴展循環(huán)賽日程表算法是分治法的一個補充，解決了任意n支隊伍的情況，但不是很通俗易懂，而且用C語言實現(xiàn)的算法不夠直觀。本文提由一種更為簡單的算法，并且利用可視化語言VisualBasic進行開發(fā)，此軟件具有界面友好、操作方便、運行可靠的特點，使用起來方便快捷。圖5參賽隊伍人數(shù)為偶數(shù)（n=10）時運行結果參考文獻：1王曉東.計算機算法設計與分析M,電子工業(yè)由版社,2001年1月.2龔沛曾，陸慰民楊志強.VisualBasic程序設計簡明教程（第2版）M.高等教育由版社，20