考場隨機(jī)分配算法研究

引言：本文采用數(shù)學(xué)建模建立隨機(jī)分配考場和座位的數(shù)學(xué)模型，然后結(jié)合算法分析設(shè)計出考場隨機(jī)分配算法，算法中提供了相應(yīng)的控制機(jī)制來智能排除重復(fù)結(jié)果保證每一位考生獲得的考場號和座位號的唯一性，并通過對影響排座算法復(fù)雜度問題的分析對算法進(jìn)行優(yōu)化。

隨著高考人數(shù)的增加和計算機(jī)技術(shù)的發(fā)展，考場編排方式逐漸由人工編排轉(zhuǎn)向了計算機(jī)自動排考。目前由于國內(nèi)高考招生考試時間短，考生考點分散，各考點的考場容量不一致，各校的考場編排需求不同等因素使得考生考場號和座位號的生成方式尤為復(fù)雜，準(zhǔn)確性和效率方面都有很高的要求。合理分配時間與空間資源以保證無沖突的發(fā)生，科學(xué)地解決考生編排和考場設(shè)置的問題是考試信息管理中的一項重要工作。本文中設(shè)計了用于實現(xiàn)計算機(jī)自動編排考場的隨機(jī)分配算法，該算法具有執(zhí)行效率高、通用性強(qiáng)、易于實現(xiàn)、隨機(jī)性強(qiáng)的特點，對高考管理工作能起到很大的促進(jìn)作用。

1 算法分析

設(shè)total 為報考相應(yīng)專業(yè)的考生總?cè)藬?shù)，count為每個考場的人數(shù)最大考生數(shù)，rc為考場數(shù)，i為考生報名編號，設(shè)集合A為已生成的考場號和座位號的元數(shù)據(jù)集合。Ai為第i為考生的考場號和座位號的二元組。（Ai∈A）

2 數(shù)學(xué)建模

公式1：Aj=f（a，b）0

其中Aj A

Aj為第j位考生的考場號和座位號，Aj應(yīng)不在已生成的考生考場號與座位號集合中。

公式2：rc=g（total， count）=total/count+1當(dāng) total mod count≠0；其中rc為考場數(shù)

公式3：b=h（count）=Random（count）+1

公式4：a=l（rc）=Random（rc）+1

3 算法描述（java語言）：

3.1考場數(shù)目計算

根據(jù)公式2得到以下算法：

int room=total%count==0？total/count：total/count+1；

3.2設(shè)置已生成考號集合

int rncode=new int [total][2]；

3.3設(shè)置考場隨機(jī)編碼

根據(jù)隨機(jī)產(chǎn)生器得到考場編碼：

Random random=new Random（）；//設(shè)置座位隨機(jī)產(chǎn)生器

int coucer=0；//設(shè)置游標(biāo)指針初值為0；

3.4考場號和座位號算法

根據(jù)公式1-4，采用循環(huán)為每一個考生計算并生成考場號和座位號，為生成考號提供了數(shù)據(jù)基礎(chǔ)。

while（coucer

int r=0，c=0；

r=random.nextInt（room）+1；//隨機(jī)獲得考場號

c=random.nextInt（count）+1；//隨機(jī)獲得座位號

//判斷當(dāng)前考場號的當(dāng)前座位是否在已生成集合中，如果在//重新生成并繼續(xù)判斷直到當(dāng)前考場號和當(dāng)前座位號不在//集合中時將其存入已生成集合。

for（int i=0；i<=coucer；i++）{

if（rncode[i][0]==rrncode[i][1]==c）{

r=random.nextInt（room）+1；

c=random.nextInt（count）+1；

i=0；

}

}

rncode[coucer][0]=r；

rncode[coucer][1]=c；

coucer++；

}

4 算法總結(jié)

該算法首先采用數(shù)學(xué)建模建立隨機(jī)分配考場和座位的數(shù)學(xué)模型，從而保證了算法的正確性和科學(xué)性。再結(jié)合算法分析，依據(jù)報考人數(shù)和考場最大人數(shù)為每一位考生隨機(jī)生成考場號和座位號。為了保證考場號和座位號的唯一性，算法中提供了相應(yīng)的控制機(jī)制來智能排除重復(fù)結(jié)果保證每一位考生獲得的考場號和座位號唯一。該算法復(fù)雜度大，執(zhí)行效率欠佳。

5 算法改進(jìn)

5.1影響算法復(fù)雜度的主要原因

通過分析我們不難發(fā)現(xiàn)，上述算法的主要開銷用在沖突檢測上，所以改進(jìn)算法的主要途徑也應(yīng)該放在改進(jìn)檢測算法上。

5.2改進(jìn)方案

為了實現(xiàn)沖突域快速定位，我們設(shè)置一個長度為total的標(biāo)志：

boolean flag =new boolean [total]；

通過檢測第m位是否為true 即可檢測沖突。考場號和座位號可依據(jù)如下公式算得：

r=m/total//獲得考場號

c=m%total//獲得座位號

5.3改進(jìn)算法實現(xiàn)

while（coucer

//生成隨機(jī)種子

int m=random.nextInt（total）+1；

//判斷種子是否存在，若存在則重新生成

while（flag[m]）{

m=random.nextInt（total）+1；

}

flag[m]=true； //設(shè)置標(biāo)志位

//根據(jù)種子生成考場和座位

int r=m/total；

int c=m%total；

rncode[coucer][0]=r；

rncode[coucer][1]=c；

//游標(biāo)自加

coucer++；

}

6改進(jìn)算法總結(jié)

改進(jìn)算法通過對影響排座算法復(fù)雜度的主要原因進(jìn)行分析，找到了大幅度降低算法復(fù)雜度的方法，使得改進(jìn)后的算法在保持原有優(yōu)點的基礎(chǔ)上，執(zhí)行效率大幅度提升，更符合實際應(yīng)用。

本算法關(guān)鍵在于數(shù)學(xué)模型的建立， 結(jié)合實際考場編排問題的一些常見約束條件和優(yōu)化目標(biāo)，提出對該問題的一種特定的解決方案，對如何合理、完善、快速的編排考場具有重要的意義。

參考文獻(xiàn)：

[l]楊穎輝，魏彩娟.運用VFP8.0實現(xiàn)CET監(jiān)考隨機(jī)分配.科技創(chuàng)新導(dǎo)報，2010.

[2]范玉順，二基工握合算法的研究生招生考試考試座位編排系統(tǒng)研究與應(yīng)用[D].中南大學(xué)碩士學(xué)位論文，2011.

[3]馮向萍，張?zhí)t，李萍.高考考場編排算法研究.新疆農(nóng)業(yè)大學(xué)學(xué)報，2008.

[4] AnanyLevitin.算法設(shè)計與分析基礎(chǔ).北京：清華大學(xué)出版社，2004.

[5]王玲.分布估計算法在排考中的應(yīng)用[D]，碩士學(xué)位論文.長沙：湖南師范大學(xué)，2008.

[6]蔡木生.高校自動排考算法的設(shè)計與實現(xiàn)[J].計算機(jī)工程與應(yīng)用 .2010.

（作者單位：隴東學(xué)院信息工程學(xué)院）

作者簡介：李娜（1980-），女，漢，西北師范大學(xué)，甘肅西峰人，講師，主要從事計算機(jī)軟件的開發(fā)與應(yīng)用研究。

基金項目：本文系甘肅省教育科學(xué)十二五規(guī)劃項目“中學(xué)數(shù)字教學(xué)資料結(jié)構(gòu)化管理方案研究”（項目編號：GS【2013】GHB0933）的研究成果之一。