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

1、單循環(huán)賽賽程安排算法研究摘要：循環(huán)賽賽程安排算法是一個(gè)很經(jīng)典的計(jì)算機(jī)算法，它是分治法的一個(gè)經(jīng)典應(yīng)用，但該算法只適應(yīng)于2n支隊(duì)伍的賽程安排問題，而對(duì)于非2n支隊(duì)伍的賽程安排問題卻沒有很好的解決。文章使用可視化語言VisualBasic作為開發(fā)工具，借助于循環(huán)隊(duì)列的規(guī)律，針對(duì)任意n支隊(duì)伍的賽程安排提由一種直觀、方便的算法。關(guān)鍵詞：單循環(huán)賽；賽程安排；算法；VisualBasic6.0中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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引言在計(jì)算機(jī)算法中，循環(huán)賽賽程安排算法是是分治法的一個(gè)經(jīng)典應(yīng)用，但該算法只適應(yīng)于2n支隊(duì)伍的賽程安

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

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

6、）:圖1循環(huán)隊(duì)列第一輪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支隊(duì)伍(2)當(dāng)比賽隊(duì)伍數(shù)為偶數(shù)即n=2*k(nA2)時(shí)，每一輪比賽只需在n=2*k(nn2)的基礎(chǔ)上補(bǔ)上輪空的隊(duì)伍和編號(hào)為n的隊(duì)伍比賽即可。例：8支隊(duì)伍參加比賽的排法(見圖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支隊(duì)伍3算法實(shí)現(xiàn)

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