自學(xué)考試考場編排尾數(shù)組合算法

1、自學(xué)考試考場編排尾數(shù)組合算法德陽市自學(xué)考試辦公室 景小松考場編排是自學(xué)考試管理系統(tǒng)中一個(gè)重要的部分。自學(xué)考試的考場編排有別于其它考試的最大特點(diǎn)是參與編排的課程數(shù)巨大，普通高考、成人高考等考試每一場考試只有一門或幾門課程，而自學(xué)考試每一場考試的課程達(dá)到一百多門。一百多門的課程數(shù)給自學(xué)考試的考場編排出了一道在其他考試中不會(huì)遇到的難題，就是如何把大量的課程尾數(shù)（對(duì)課程報(bào)考科數(shù)用考場容量取余的結(jié)果稱為課程尾數(shù)，簡稱尾數(shù)，在這里尾數(shù)為0的除外）按要求組合起來。目前自學(xué)考試編排考場的要求是：1.考場人數(shù)不超過考場容量（考場最多可容納的人數(shù)稱為考場容量，現(xiàn)為30人）；2.考場課程門數(shù)不超過規(guī)定門數(shù)，即課程容

2、量（現(xiàn)為6門）；3.課程尾數(shù)不能分割；4.編排的考場數(shù)應(yīng)盡量與最佳考場數(shù)接近（最佳考場數(shù)是指考場總報(bào)考科數(shù)對(duì)考場容量向上取整的結(jié)果）?？紙鼍幣诺目紙鰯?shù)與最佳數(shù)相等或盡可能接近是自學(xué)考試考場編排中最基本的要求，一方面減少考場數(shù)，節(jié)約考試經(jīng)費(fèi)，另一方面減少人工調(diào)整，提高了工作效率。自學(xué)考試考場編排中最為核心的工作就是大量課程尾數(shù)組合，尾數(shù)組合算法的優(yōu)劣直接關(guān)系到編排的效率以及對(duì)考場數(shù)的影響。本文所探求的就是找到一種最佳尾數(shù)組合算法來達(dá)到這一目的。為了更好地設(shè)計(jì)考場編排的尾數(shù)組合算法，我們先來分析一下考場編排中最重要的對(duì)象課程尾數(shù)?？紙稣n程尾數(shù)分析。自學(xué)考試每次開考課程達(dá)幾百門，平均每場近百門。以四

3、川省2008年10月份為例，共開考課程470門，平均每場115門，每場課程尾數(shù)也近百（除開整除的情況）。不同規(guī)模的考點(diǎn)，課程尾數(shù)出現(xiàn)是有一定的規(guī)律的。小規(guī)?？键c(diǎn)（每場十個(gè)考場左右或以下）一般情況下課程報(bào)考人數(shù)少，容易產(chǎn)生大量的小尾數(shù)，我們稱之的小尾數(shù)（型）考點(diǎn)，所以在考場編排時(shí)經(jīng)常遇到幾個(gè)不足十人的考場，為了節(jié)約經(jīng)費(fèi)，有的考點(diǎn)常常把兩三個(gè)考場合為一個(gè)考場（當(dāng)然是考務(wù)上的操作）。在考場編排算法中，課程容量的可調(diào)整，對(duì)這些小考點(diǎn)來說也是一種方便。縣區(qū)考點(diǎn)一般情況下都是小考點(diǎn)（除開有高校的縣區(qū)），這部分縣區(qū)考點(diǎn)占所有考點(diǎn)的大部分，所以在考場編排中要充分考慮大部分考點(diǎn)的情況。大中型考點(diǎn)（每場二十考場左

4、右或以上）一般情況下課程報(bào)考人數(shù)多，課程尾數(shù)的分布相對(duì)均勻，我們稱為尾數(shù)均勻（型）考點(diǎn)。大型考點(diǎn)可能出現(xiàn)比較特殊的大量大尾數(shù)，我們稱為大尾數(shù)（型）考點(diǎn)。有些中型考點(diǎn)小尾數(shù)也較多，主要出現(xiàn)在冷偏專業(yè)的課程上。大中型考點(diǎn)主要分布在大中型城市。我們把考場編排結(jié)果按照考場內(nèi)的尾數(shù)特征來進(jìn)行一個(gè)分類：一類是由幾個(gè)小尾數(shù)組成的考場，如5+2+2+1+1+1，尾數(shù)和不大于15，稱為小尾數(shù)考場；一類是由一個(gè)大尾數(shù)組成的考場，如29、28等，稱為大尾數(shù)考場；一類是由一個(gè)中尾數(shù)組成的考場，如16，17等，稱為中尾數(shù)考場。這三類考場都達(dá)不到考場容量稱為不滿考場，其余的尾數(shù)組合達(dá)到考場容量的稱為滿考場。考場編排合理的

5、情況下，每場不滿考場只有一到兩個(gè)，且考場余數(shù)和不大于考場容量。現(xiàn)有系統(tǒng)中考場編排算法分析。我們先來分析一下現(xiàn)在四川省自學(xué)考試管理系統(tǒng)中考場編排算法。從只有一個(gè)考點(diǎn)的自動(dòng)編排結(jié)果分析來看，最后幾個(gè)考場往往是小尾數(shù)集中的小考場。從尾數(shù)的組合情況來看，是從大尾數(shù)開始，向下找到合適的最大的一個(gè)尾數(shù)，達(dá)到或盡量接近考場容量（30），不足考場容量的再如此循環(huán)一次，循環(huán)次數(shù)不超過課程容量（6）。我們把這種算法稱為先大法。先大法算法簡單，比較容易通過語言實(shí)現(xiàn)。先大法的算法流程圖如下：賦給這組尾數(shù)一個(gè)考場號(hào)，并從排序中刪除它們未達(dá)到存在存在達(dá)到尾數(shù)從大到小排序選擇最大尾數(shù)賦給P結(jié)束不存在不大于30-P的最大尾數(shù)

6、Q不存在達(dá)到課程容量P=P+Q先大法對(duì)于尾數(shù)均勻分布的大中型考點(diǎn)比較合適，也容易達(dá)到最佳考場數(shù)，一般情況下比最佳考場數(shù)要多出一至兩個(gè)考場。但先大法對(duì)于存在大量小尾數(shù)的小考點(diǎn)是不合適的，編排結(jié)果往往會(huì)出現(xiàn)多個(gè)小尾數(shù)考場，比最佳考場數(shù)多出二至三個(gè)甚至四個(gè)考場。小尾數(shù)較多的中型考點(diǎn)也容易出現(xiàn)這種情況。大多數(shù)情況下，通過人工調(diào)整，每場都可以減少一至兩個(gè)考場?；旧厦恳粓龆夹枰斯ふ{(diào)整來減少考場，增加了工作量，算法設(shè)計(jì)不合理，編排效率不高。所以先大法對(duì)于大多數(shù)中小型考點(diǎn)的考場編排是不合適的。在先大法中，人工調(diào)整是必須要做的工作，由于要人工參與，效率不高。那么，我們是否可以把人工調(diào)整設(shè)計(jì)成算法來實(shí)現(xiàn)，減少

7、人工成分，提高系統(tǒng)效率和工作效率呢？我們先來分析一下人工調(diào)整的過程，這實(shí)際上就是調(diào)整算法的設(shè)計(jì)。先大法容易產(chǎn)生多個(gè)小尾數(shù)考場，當(dāng)兩個(gè)小尾數(shù)考場相加不足考場容量的，我們一般可以通過調(diào)整來減少一個(gè)考場。我們把兩個(gè)小尾數(shù)考場的尾數(shù)統(tǒng)一調(diào)整，通過排序，從大到小，先把最大的幾個(gè)尾數(shù)組合（比課程容量少一，5個(gè)），計(jì)算出它們的和數(shù)（如5+3+2+2+1），在已編排好的有兩個(gè)尾數(shù)的考場中尋找是否有這個(gè)和數(shù)，如有(如13+17)，則把這個(gè)尾數(shù)與尾數(shù)組合對(duì)換（17+5+3+2+2+1，13），如無，則在尾數(shù)排序中減少尾數(shù)組合和（如5+3+2+1+1），又循環(huán)一次，直至找到與尾數(shù)組合相對(duì)應(yīng)的已組合尾數(shù)，如無，則尾數(shù)

8、組合個(gè)數(shù)減少1，在已編排好的有三個(gè)尾數(shù)的考場中尋找與組合和匹配的尾數(shù)。尾數(shù)組合的個(gè)數(shù)遞減參與外圍循環(huán)。循環(huán)直到所要調(diào)整的尾數(shù)個(gè)數(shù)等于或小于課程容量（6個(gè)）為止，然后再看有無要調(diào)整的小尾數(shù)考場。雖然還有其它的人工調(diào)整的方法，但不好程式化，這里只介紹這一種小尾數(shù)考場的合并算法，算法流程圖如下：否否否否存在存在不存在不存在是是是兩考場尾數(shù)統(tǒng)一從大到小排序，N=5，M=2兩考場人數(shù)相加不大于30，尾數(shù)個(gè)數(shù)大于6從大到小選擇N個(gè)尾數(shù)，記和為P在編排好的尾數(shù)個(gè)數(shù)為M的考場中有否有值為P的尾數(shù)組合個(gè)數(shù)N不變，找到小于P的最大值，并記為P將尾數(shù)組合與找到的尾數(shù)對(duì)換，將這組尾數(shù)從排序中刪除，尾數(shù)個(gè)數(shù)是否為N對(duì)換

9、尾數(shù)與剩余尾數(shù)組合為一考場組合個(gè)數(shù)N不變，組合和P是否為最小值N=N-1，M=M+1N=2開 始結(jié) 束對(duì)換尾數(shù)與剩余尾數(shù)個(gè)數(shù)大于6是先大法編排尾數(shù)調(diào)整算法比較復(fù)雜，它把人工調(diào)整的整個(gè)過程程式化，雖然算法實(shí)現(xiàn)起來比較困難，但卻提高了編排設(shè)計(jì)的效率，減少了人工調(diào)整的環(huán)節(jié)。在先大法中，第一個(gè)組合的尾數(shù)有可能不是最合適的，使得考場尾數(shù)組合達(dá)不到考場容量。如：18、7、6、3、3中，先大法組合為：18+7+3=28，達(dá)不到30。而次大尾數(shù)組合18+6+3+3=30，就比先大法組合要好。所以在先大法組合中可以加入兩次次大組合，選擇最接近考場容量的組合。我們稱這種算法為試探法。如果我們在先大法中加入試探法后

10、，對(duì)每一場又進(jìn)行調(diào)整算法進(jìn)行程式調(diào)整，則使得考場編排更加自動(dòng)化，更加合理和高效。其它思路的尾數(shù)組合算法。對(duì)于大多數(shù)縣區(qū)考點(diǎn)，先大法往往會(huì)產(chǎn)生許多小尾數(shù)考場，在考場編排時(shí)要進(jìn)行大量的人工調(diào)整。這是由先大法本身算法所決定的，先大法中總是先選大尾數(shù)來組合，最后小尾數(shù)余下的就比較多，從而出現(xiàn)了許多的小尾數(shù)考場。為了防止大量小尾數(shù)的剩余，可以在選擇尾數(shù)時(shí)，用試控法，選擇最接近考場容量，并且尾數(shù)個(gè)數(shù)最多的一組。當(dāng)然，我們也可以重新設(shè)計(jì)一種尾數(shù)組合的算法來消除小尾數(shù)考場。我們可以用與先大法相反的思路來設(shè)計(jì)新的算法，先選擇最小的尾數(shù)來組合，如此循環(huán)，在最后一次循環(huán)時(shí)用先大法來達(dá)到或接近考場容量。我們稱這種算法

11、為先小法。先小法的算法流程圖與先大法大同小異，可參考先大法算法流程圖。先小法雖然可以解決先大法中小尾數(shù)考場的問題，但新的問題也就產(chǎn)生了。先小法中小尾數(shù)優(yōu)先，使得中尾數(shù)大量剩余，如14、17、18等，形成幾個(gè)無法組合的中尾數(shù)考場。在現(xiàn)在的考務(wù)管理中，尾數(shù)不允許分割。實(shí)際上，尾數(shù)分割在考務(wù)操作上是可行的，分割后，可以通過增加試卷袋解決考務(wù)操作。如果允許尾數(shù)分割，中尾數(shù)考場的問題就迎刃而解了。如上例中，我們可以把14分割為12+2，可產(chǎn)生18+12與17+2的合理組合，這樣就減少了一個(gè)考場，一般情況下，只進(jìn)行一至兩次分割操作就可以達(dá)到最佳考場數(shù)。我們稱這種算法為分割算法。在先大法與先小法中都是以最大

12、的尾數(shù)開始組合尾數(shù)，往往會(huì)產(chǎn)生小尾數(shù)或中尾數(shù)的剩余而產(chǎn)生一些組合上不合理的問題。我們是否可以考慮從中間的某一個(gè)尾數(shù)開始用先小法組合，最后進(jìn)行最大尾數(shù)的組合，一方面可以消除中尾數(shù)無法組合的情況，另一方面也防止了小尾數(shù)的剩余。我們稱這種算法為中點(diǎn)法。中點(diǎn)法中，中小尾數(shù)先被組合，容易形成大尾數(shù)考場，但考場余數(shù)和一般不會(huì)大于考場容量，與最佳考場數(shù)相等或最接近，所以，中點(diǎn)法相對(duì)于先大法和先小法較為合理。在中點(diǎn)法中，關(guān)鍵是開始組合的尾數(shù)的選擇，也就是中點(diǎn)的選擇。我們設(shè)計(jì)了一種比較簡單合理的中點(diǎn)選擇法：我們把所有的尾數(shù)相加的和對(duì)考場容量向上取整（既取整有余則取整數(shù)加一），所得的數(shù)稱為最小組合考場數(shù)，能達(dá)到最

13、小組合考場數(shù)就能達(dá)到最佳考場數(shù)。把尾數(shù)從大到小排序后，中點(diǎn)就是最小組合考場數(shù)所對(duì)應(yīng)的記錄。我們以中點(diǎn)為界，把大尾數(shù)的考場余數(shù)比為“坑”，小尾數(shù)比為“石頭”，最小組合考場數(shù)就是我們要填的“坑”的最小數(shù)目。中點(diǎn)可以形象地比做成“坑”與“石頭”之間的供求平衡點(diǎn)。以考場容量為30例，如果中點(diǎn)大于15，就會(huì)出現(xiàn)“坑小石頭大”無法組合的情況，所以，一般情況下中點(diǎn)不能大于15。中小型考點(diǎn)由于存在大量的小尾數(shù)，中點(diǎn)一般不會(huì)大于15，但對(duì)于大型考點(diǎn)有可能出現(xiàn)大量的大尾數(shù)，這時(shí)中點(diǎn)就可能大于15。中點(diǎn)大于15時(shí)，在尾數(shù)不允許分割的情況下，只能通過增加考場數(shù)來容納從16到中點(diǎn)的這部分無法填“坑”的大“石頭”，從而下

14、移中點(diǎn)至15，下移幾個(gè)記錄，則考場數(shù)就增加幾個(gè)。當(dāng)然，如果允許尾數(shù)分割，就不用增加考場。遍歷算法。在上述的幾種算法中，都是一個(gè)考場尾數(shù)組合完畢后進(jìn)行下一個(gè)考場尾數(shù)組合，我們統(tǒng)稱為逐場（個(gè)）法。逐場法中，往往是先滿足所組合考場的條件，沒有考慮全局，難免產(chǎn)生這樣那樣的問題。為解決這個(gè)問題，我們可以選擇較為合理的中點(diǎn)法，用遍歷法來分配所有的尾數(shù)。我們以中點(diǎn)為界，從中點(diǎn)這個(gè)最大的“坑”開始向每個(gè)“坑”填“石頭”，總是用最大的“石頭”來填“坑”，一次遍歷一個(gè)“坑”只用一個(gè)“石頭”；填滿的“坑”就不再參與遍歷；如此遍歷幾次（最多為課程容量的次數(shù)，6次，如果沒有課程容量的限制，則可一直遍歷下去，但一般情況下

15、，遍歷次數(shù)不會(huì)超過9次），由于供求平衡，所以最后“石頭”會(huì)用完；如果在遍歷了課程容量所規(guī)定的次數(shù)后仍有尾數(shù)剩余，則剩余尾數(shù)按先大法組合，從而出現(xiàn)個(gè)小尾數(shù)考場，這種情況往往會(huì)出現(xiàn)在有大量小尾數(shù)的考點(diǎn)。遍歷時(shí)，可以用上述的固定“坑”遍歷，也可以用動(dòng)態(tài)“坑”遍歷，也就是每次遍歷前都對(duì)未填滿的“坑”從大到小排序，然后從最大的“坑”開始用先大法填“坑”。動(dòng)態(tài)遍歷比較合理，但較固定遍歷用語言實(shí)現(xiàn)起來比較困難。中點(diǎn)遍歷法中雖然仍是用先大法來填“坑”，但一次遍歷時(shí)只準(zhǔn)用一次先大法，這樣，大中小尾數(shù)的組合都兼顧到了，出現(xiàn)中尾數(shù)考場及小尾數(shù)考場等問題的機(jī)率大大降低，基本上不會(huì)出現(xiàn)需要調(diào)整的情況。動(dòng)態(tài)遍歷算法的流程

16、圖如下（有些步驟簡化省略）：存在否存在是不存在存在不存在不存在建立“坑”數(shù)組（30-尾數(shù)值，是一個(gè)二維數(shù)組）和“石”數(shù)組，并降序排序選擇最大的“坑”P選擇不大于P的“石”RP-R=0賦給所對(duì)應(yīng)的尾數(shù)組合一個(gè)考場號(hào)，并在排序中刪除選擇下一個(gè)“坑”并賦給P結(jié) 束開 始“坑”數(shù)組重新排序（此時(shí)“坑”值應(yīng)減去所填“石頭”）找中點(diǎn)，調(diào)整中點(diǎn)（略）在遍歷法中，也會(huì)出現(xiàn)一些特殊的情況。比如，中點(diǎn)為第一個(gè)15記錄，中點(diǎn)附近尾數(shù)分布情況為：18、17、16、15、15、15、14、14、13，明顯的一點(diǎn)是，有一個(gè)15和一個(gè)14的“石頭”無法用上。也就是說，有許多大“石頭”，而能容納大“石頭”的“坑”少，這時(shí)用遍

17、歷法，最后這部分大“石頭”就無法找到合適的“坑”，而有些“坑”卻沒有填滿。在允許尾數(shù)分割時(shí)，問題比較容易解決，用“碎石”的方法即可，而且能達(dá)到最佳考場數(shù)。但不允許分割尾數(shù)時(shí)，就必須把這部分“石頭”的一些轉(zhuǎn)化為坑，一般情況下，只須轉(zhuǎn)化一到兩個(gè)，也就是中點(diǎn)的下移一到兩個(gè)記錄，問題即可解決，但每轉(zhuǎn)化一個(gè)就要比最佳考場數(shù)多出一個(gè)考場。所以，在尾數(shù)不允許分割的情況下，中點(diǎn)選定后（除開中點(diǎn)大于15的情況，因?yàn)橹悬c(diǎn)大于15時(shí)，本身就要增加考場，使中點(diǎn)移到15。），先計(jì)算最大和次大“石頭”的個(gè)數(shù)SS，然后計(jì)算能容納這兩種“石頭”的“坑”的個(gè)數(shù)SK。如SS>SK，即大“石頭”個(gè)數(shù)大于大“坑”個(gè)數(shù)，就需把中

18、點(diǎn)下移，下移記錄數(shù)為SS-INT（SS-SK）/2），INT為取整運(yùn)算。對(duì)考場編排的一些建議。上面我們對(duì)課程尾數(shù)進(jìn)行了分析，對(duì)尾數(shù)的組合算法進(jìn)行了比較，在解決一些算法缺點(diǎn)中，加入了調(diào)整算法、試探算法、分割算法、中點(diǎn)選擇算法、轉(zhuǎn)化算法等。在對(duì)比先大法、先小法、中點(diǎn)法、遍歷法等算法中，比較而言，遍歷法是比較合理和高效的算法。在所有算法中先大法是基礎(chǔ)算法，遍歷法是在中點(diǎn)法的基礎(chǔ)上發(fā)展的。由于目前的自學(xué)考試管理系統(tǒng)中考場編排用的是最容易實(shí)現(xiàn)但效率最低的先大法，需要大量的人工調(diào)整工作，所以建議考場編排采用動(dòng)態(tài)遍歷法，這種算法是所有算法中最復(fù)雜的，用編程語言實(shí)現(xiàn)起來困難一些，但卻是編排最為合理的、效率最高的算法。我省大部分考點(diǎn)是中小型考點(diǎn)，在考場編排時(shí)，應(yīng)從經(jīng)濟(jì)和效率角度多考慮?？紙鼍幣诺乃膫€(gè)規(guī)則中，除開最佳考場數(shù)這一要求外，其余的三個(gè)都是可以變化和改動(dòng)的?？紙鋈萘吭酱?，編排的考場數(shù)就越少，原來自學(xué)考試的考場容量是25人，現(xiàn)在為30人，考場數(shù)可減少1/6，相應(yīng)的考試經(jīng)費(fèi)也可節(jié)約不少，如果能把考場容量設(shè)為35（5*7）人，則又可以減少近1/7的考場數(shù)。現(xiàn)在大學(xué)和高中的標(biāo)準(zhǔn)教室可以達(dá)到考場容量為35人，可以考慮把考場容量擴(kuò)大為35人