【正文】 j++) if (relation[pnam][j] == 1) p in_degree = p in_degree + 1。 while(p != NULL) { for(int i = 0。 relation[rnam][pnam] == 1 || relation[rnam][pnam] == 0 amp。 } p = q。 } k = 0。 r = head。 } int l = 0。 p in_degree = 0。 head stu = 0。}附3：逆著色算法函數(shù)clas* get_painted (int relation[clas_num][clas_num], int student_sum[clas_num]) { ………… clas *head = new clas。 head small = s。 cap_now = total_cap(l, m, s)。 s_max = stu_num / s_cap + 1。 headcapacity = headlarge = headmid = headsmall = 0。 j ++) { if(temp[j (num_gonggong + num_bixiu + num_yuanxuan)] != 0) stu_cour[j] = temp[j (num_gonggong + num_bixiu + num_yuanxuan)]。 j num_gonggong + num_bixiu + num_yuanxuan。 j num_bixiu。 i college。通過觀察幾種考試安排方案的時間容量曲線，比照其優(yōu)劣排名，發(fā)現(xiàn)一個規(guī)律：曲線的震蕩程度影響學生和教師的滿意度；震蕩頻率增大時教師的滿意度提高，振幅接近穩(wěn)定時學生的滿意度提高。參照對“教師滿意”的定義，我們用教師監(jiān)考的連續(xù)兩場考試之間時間間隔的方差倒數(shù)的十倍表征這個教師的滿意程度，用所有教師滿意度的均值作為評價每種方案優(yōu)劣的指標之一。對于學生，參照對“學生滿意”的定義，第一條已保證滿足，只需考慮考試安排均勻程度這一個因素的影響。 圖中橫軸表示按時間先后安排的考試場次（共計40場），縱軸表示在本時間段內(nèi)參加考試的考生總數(shù)。分入40個時間段說明8天時間就可以安排完所有考試，這與現(xiàn)實情況中許多高校安排“考試周”的事實是一致的。4　 每個學生從8門院系選修課程中選修12門，且不同學院具有的院選課各不相同5　 每個學生從140門公共選修課程中選修12門。④、按上述順序?qū)⒗蠋熞来畏峙淙肟荚嚾粘讨腥孕璞O(jiān)考的考場，以保證每個老師監(jiān)考場次接近（）至此安排考試的全過程敘述完畢。 （5）、先考大容量課程，再考小容量課程，橫向分配即，將即將所有時間段按其包含的考生總數(shù)由多到少排序后進行橫向分配，排滿整個日程表。其余的時間段可能包含多門課程，按上述原則2安排。這是為了使更多的學生先結(jié)束所有考試。具體描述如下：①、分別估算大、中、小教室需求的上限。因為教室安排時遵循的原則是使每門考試占用的教室數(shù)目盡量少，所以，第門課程考試需要教室的數(shù)量可以由第門課程的選修學生數(shù)除以大型教室可容納的考生人數(shù)后向上取整直接求得，即， （1）每個教室安排兩名監(jiān)考教師，則同一時間的考試科目（假設(shè)為）必須滿足以下不等式： （2）其中為監(jiān)考教師總?cè)藬?shù)。2　 由于我們只是假設(shè)用作考場的教室在大面積課程錯開的前提下數(shù)量充足，故圖G中任意兩門大面積課程間必須人為地以邊相連，否則如果出現(xiàn)同時舉辦大面積考試則教室可能會不夠用。算法的有效性見第五部分模型檢驗。1　 遍歷圖，找出度數(shù)大于零且度數(shù)最小的節(jié)點X。構(gòu)建簡單無向圖H = (V，E)，其中H(V) = {D1，D2...，Dn}，每一條邊DiDj(DiDj∈E)的兩個端點Di和Dj表示這兩門課程可以安排在同一場次考試。定義[圖的逆著色]：圖G的一個逆著色是指k種顏色1，2，...，k對于G節(jié)點的一 個分配，使得一種顏色的任意兩個節(jié)點都相鄰。每個老師盡量監(jiān)考他所教授的科目，并滿足使老師滿意的條件。216。216。這里為了簡化而不考慮上述情況，即，我們認為只要大面積考試不同時出現(xiàn)，就有足夠的教室用于安排同一時間的所有考試。三. 符號說明：第門課程：監(jiān)考教師的數(shù)量：大型教室可容納的考生人數(shù)：中型教室可容納的考生人數(shù)：小型教室可容納的考生人數(shù)：第個考試時間段：考試總天數(shù)：學生滿意度：教師滿意度四. 問題分析及模型建立（一）問題分析容易看出錯開各個學生的考試時間是安排方案的前提要求：存在學生考試時間沖突的考試安排方案無疑是失敗的。歸納起來欲解決的問題有：1. 必須保證不會出現(xiàn)同一學生有兩門考試時間沖突；；2. 合理利用容量不同的考場；3. 安排應盡量合理，使學生、教師和學校都滿意。為了滿足2和4，我們將討論幾種考試時間分配方案并從中得到令學生、老師以及學校都滿意的最優(yōu)者。為了檢驗模型的科學性與可行性，我們設(shè)計了一個選課程序，使得可以利用計算機對大批量學生的選課情況進行模擬，以得到一個較為接近實際的選課總表?？紤]到實際的高校規(guī)模，這個建模問題只有在做到用計算機進行大樣本仿真處理的情況下才算得到真正意義上的解決：手工安排顯然是難以完成的。本文通過運用圖論中的著色算法確?？荚嚐o沖突，并遵循時間盡量短的原則。這是基于假設(shè)2“一個學校的學生選課情況足夠交錯復雜以致能排在同一時間的考試科目不會過多”的。 對教室分配合理的理解：在安排每門考試時，以占用教室數(shù)最少為原則；在此基礎(chǔ)上，使對于每間考場，空置的位置最少。 對方案使學校滿意的定義： 使考試持續(xù)的總時間盡量短；設(shè)計的安排方案應該簡便易行，不致過于繁復，難以實現(xiàn)。（二）模型設(shè)計1. 分配各門考試的時間。而G的逆色數(shù)是指G逆著色數(shù)k的最小值。于是考試最少需要安排的場次等于圖H的逆色數(shù)。2　 圖是否有邊存在，沒有則算法結(jié)束。（4）針對其他要求及程序?qū)崿F(xiàn)的一些問題的說明1　 用程序?qū)崿F(xiàn)算法（3）時必須注意的是合并節(jié)點X和Y的過程。3　 實現(xiàn)算法的程序中，我們用零一矩陣（對稱陣）表示圖。對每一組考試，用不等式（2）進行檢驗，若不滿足，則將其拆分為總參加考試人數(shù)近似相等的兩組。如對于大教室， + 1。（） 說明：近似認為一天當中的5個時間段間隔均勻，而第一天的最后一次與第二天的第一次考試時間間隔是一天之內(nèi)兩次考試間隔的4倍。（2）、先考大容量時間段，再考小容量時間段即將所有時間段按其包含的考生總數(shù)由多到少排序，再按此順序排滿整個日程表。至此，各門考試科目的教室安排和時間安排都已經(jīng)確定。五. 模型求解及模型檢驗（一）模型使用的案例的獲得為了更好地檢驗模型是否有效、可行，首先需要一個接近實際的待安排案例。6　 根據(jù)上述說明，可選課程總數(shù)是300門，它們都將在期末進行考試。程序運行后給出的部分結(jié)果如下：考試的時間段組合及教室分配（部分）…… …… 131 4 large: 3 middle: 0 small: 1 71 3 large: 3 middle: 0 small: 0 31 3 large: 2 middle: 0 small: 1 21 3 large: 2 middle: 0 small: 129 152 4 large: 3 middle: 1 small: 0 112 4 large: 2 middle: 2 small: 0…… ……