基于遞歸分治折半算法的隨機考場排布新方法

【摘要】 21世紀是一個數字化、網絡化、信息化的時代。在排布考場時，考慮到考生即時打印準考證的需求，系統先將考場座位隨機排布，然后再等待考生按報名次序對號落座。在充分考慮隨機性的前提下，為減少考場浪費，又運用遞歸的基本原理采用分治思想，提出了遞歸分治折半算法這一考場排布的新方法。

【關鍵詞】考場排布，遞歸分治折半算法

隨著社會競爭的日益激烈，考生和社會各界都要考試考場的安排要做到“公開、科學、公平、公正”。雖然各種各樣的考試對考場排布的要求不盡相同，但防止考生作弊和監考舞弊現象是其共同的目的，在編排考場時要求同一屬性的考生盡量分散，從而減少串通舞弊的現象。目前經常使用在考試中的考場編排算法主要有線性隨機法、兩級隨機法、折半法、環形插入法、完全隨機發、混洗法等幾種。本算法的目的是在讓考生能即時打印準考證，并盡可能地將考生隨機分散到考場中去。

由于考生最后的報名情況事先不可預知，所以放棄將所有考生放在一起進行隨機排布座位的做法，轉而將虛擬座位與實際考場建立對應的關系再進行考場排布，最后把經過排序后的虛擬座位重新編號形成新的序列。在某個考生報名結束后，根據他自身的報名順序從序列中獲取虛擬座位的考場排布信息，也就與和虛擬座位對應的實際考場座位產生了對應關系。由于在報名之前就可以利用虛擬座位進行考場排布，也就做到了隨時報名隨時打印準考證。

利用虛擬座位考場排布法也存在缺點。問題主要存在于安全性上。由于考生的考場資料長期存放在服務器上，所以對服務器的安全就有了更高的要求。只要數據存儲在服務器之中，這個問題就無法徹底解決。雖然無法徹底解決，但可以對服務器進行保護。采用基于B/S的三層結構，用戶工作界面是通過瀏覽器實現，極少部分事務邏輯在前端實現，主要事務才在服務器端實現。這很大程度上緩解了服務器的安全壓力。再加上對服務器的安全防護，可以阻擋絕大部分的服務器攻擊。

除了安全性問題，虛擬座位考場排布法還產生了兩個新問題：

1．如果事先排布的考場數量不夠，報名晚的考生將不能獲取正確的考場排布信息。

2．如果報名的考生數量大大小于事先排布的考場座位數量，將造成考場的大量浪費。

這兩個制約條件都與考生的報名數量和事先排布的考場數量有關。最好的配合就是考生的報名數量剛剛好能放滿事先排布的考場數量。由于考生報名情況的不可預知，自然需要的考場數量也是不可預知的。雖然理論上可以通過無限多考場進行排布來解決這個問題，但實際操作時是行不通的。當然我們也可以用遠大于考生數的考場座位數來排布考場，這個也不會產生考場數量不足的問題，但是這樣做的同時也大大增加了考場的浪費。

有一種十分簡單的方法可以實現準考證的即時打印——即將考生按報名順序排入考場。也就是將第一個考生排在第一考場的第一個座位，然后依次排下去。使用這樣的考場排布法優點在于考場的浪費非常小。假設每個考場的座位數是30個，最多也只會浪費29個座位。但這樣考場排布法存在一個很大的缺點：同一屬性的考生很容易會排在相鄰的座位。如果同一所中學畢業的考生在學校的組織下同時報名，就很容易被排在相鄰的座位上。而這樣的考場排布法很容易產生串通作弊的現象，所以采用這種自然隨機的辦法來排布考場是不合適的。

遞歸算法是一個直接或間接地調用自身的算法。它的載體遞歸函數是一個使用函數自身給出定義的函數。在計算機算法設計與分析中，使用遞歸技術往往使函數的定義和算法的描述簡潔且易于理解。

運用遞歸分治的基本思想，我們嘗試將需要排布的考場分割成若干個小考場，然后按順序分別排序?？忌鷪竺麜r先取得前面小考場的座位，當前一個小考場排滿了以后，后續的考生才能取得后一個小考場的座位。在所有考生完成報名后或報名時間截止后，管理員就能獲得最終的考場排布情況。按照上述的排布方法就能將考場的浪費控制在最后一個小考場的范圍之內。但如何將大考場分成一個一個的小考場又是很值得研究的問題。如果將大考場平均分配成若干個小考場，那么最大的可能考場浪費數量為任意一個小考場的數量。這樣的排布方法雖然較之全部考場一起排布的方法，浪費少了很多。但如果小考場劃分的不夠多，考場浪費依然嚴重。在權衡了前文所述的種種算法，并結合實際需求，采用遞歸分治折半加隨機算法的方式來實現考場的排布算法。算法先將所有考場按照每次對半開的方法分成若干個小考場，再將小考場中所有的座位放在一起運用隨機算法排布考場。設某次考試預計有20個考場，每個考場有30個座位。A1={a1，a2，a3…a20}為考場總集合，每個考場的座位集合為an={an1，an2，an3，…an30}。首先將A1按照遞歸分治折半的方法分成A11={ a1，a2，a3…a10}，A12={ a11，a12，a13，a14，a15 }，A13={ a16，a17}，A14={ a18，a19}，A15={ a20 }然后分別對這些考場子集中的考場座位集合進行隨機算法的排布。這里的隨機算法可以采用上述的多種算法中的一種、多種或多重使用，以達到充分隨機防止串通作弊的目的。而將考場分為由大到小的子集的目的是減少考場浪費。這種算法非常適合規模大的。先進現在使用網上報名方式的考試規模都起碼在千人以上，所以使用這種算法來實現系統的考場排布算法是十分合適且經濟的。

【參考文獻】

[1]王曉東.計算機算法設計與分析[M]. 北京：電子工業出版社，2004.

[2]馮向萍. 高考考場編排算法研究[D] .新疆農業大學，2008.