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

1、自學(xué)考試考場編排尾數(shù)組合算法德陽市自學(xué)考試辦公室 景小松考場編排是自學(xué)考試管理系統(tǒng)中一個重要的部分。自學(xué)考試的考場編排有別于其它考試的最大特點是參與編排的課程數(shù)巨大，普通高考、成人高考等考試每一場考試只有一門或幾門課程，而自學(xué)考試每一場考試的課程達到一百多門。一百多門的課程數(shù)給自學(xué)考試的考場編排出了一道在其他考試中不會遇到的難題，就是如何把大量的課程尾數(shù)（對課程報考科數(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ù)是指考場總報考科數(shù)對考場容量向上取整的結(jié)果）。考場編排的考場數(shù)與最佳數(shù)相等或盡可能接近是自學(xué)考試考場編排中最基本的要求，一方面減少考場數(shù)，節(jié)約考試經(jīng)費，另一方面減少人工調(diào)整，提高了工作效率。自學(xué)考試考場編排中最為核心的工作就是大量課程尾數(shù)組合，尾數(shù)組合算法的優(yōu)劣直接關(guān)系到編排的效率以及對考場數(shù)的影響。本文所探求的就是找到一種最佳尾數(shù)組合算法來達到這一目的。為了更好地設(shè)計考場編排的尾數(shù)組合算法，我們先來分析一下考場編排中最重要的對象課程尾數(shù)?？紙稣n程尾數(shù)分析。自學(xué)考試每次開考課程達幾百門，平均每場近百門。以四

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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