大學聯考分發程式及其相關問題探討
Study of the Distribution Program
for the Joint Entrance Examination of Universities and Related Problems
摘要
聯考是許多人的共同經驗，這其中又以大學聯考受到大眾較多的關注，民國七十三年起，大學聯考制度做了大幅度的修改，引發社會大眾許多的討論。本論文根據實作的經驗，對大學聯考分發程式做一詳盡的介紹，首先討論大學聯考電算作業，以及如何分發，接著提出分發程式的演算法，並探討電腦分發背後的精神與意義，以及所遇到的種種問題。文中並將對大學聯考相關問題提出討論。
關鍵詞 大學聯考、分發、回溯、循環鏈結、同分
ABSTRACT
Attending the joint entrance examination is a common experience for most
of the people, especially the joint entrance examination of universities
(abbreviation as JEEU). The institution of the JEEU has been changed from time
to time since 1984, and has initiated many discussions.
According to the implementation experiments, this paper will discuss the
distribution program for the JEEU in detail. Firstly, I discuss the computer
operation system for the JEEU. How and the distribution work function? And then
I introduce the algorithms of the distribution program and discuss the spirit
and the meanings behind the JEEU, as well as many problems we encounter. I also
discuss some other related problems within the JEEU.
keyword Joint Entrance Examination of
Universities(JEEU)、Distribution、Backtracking、Circular Chain、Same Scores
1 緣起
在台灣成長的小孩，除了接受完義務教育後就出社會工作的人之外，大部分都經過各種考試的洗禮，高中職聯招、五專聯招、四技/二專/二技聯招、大學聯招、研究所考試…大多數的聯考在暑假期間舉行，於是，每年七、八月被戲稱為「烤季」。雖然，目前教育改革的理念，希望能廢除一試訂終身的現象，甚至主張廢除聯考制度，然而，社會上仍有為數不少的人贊成聯考制度，認為這是較客觀公平的方式，而考試制度卻也有其貢獻，一個人可以透過努力讀書，改變他原本的社會階級，給願意奮發向上的人提供一個很公平的機會。
以聯考為例，因為參加考試者眾，考試的遊戲規則是否公平，就成為大家關注的焦點。這其中，又以大學聯招受到更多的矚目，不僅因為它是全國性的，而且進大學等於接受高等教育，身處注重文憑的台灣社會裡，擠進大學窄門是眾多學子的夢想、父母的期盼、鄉里的榮耀。
大學聯考在民國七十三年時，受到社會大眾極大的關注，因為遊戲規則變得複雜了，聯招會容許參加聯招的各科系自行訂定該科系的加重計分標準，最多定三科，每科最多加重50%，且採取了先考試後填志願的方式。這樣的改變，讓許多人不知所措。而原來的加重計分方式為：文法商（乙丁組）固定國文加重25%，理工醫農（甲丙組）固定數學加重25%。
不知所措的主要原因是社會大眾對科系排名的迷思，新制讓人直覺地以為排名將會打亂（雖然事實上程度輕微），填志願變得更加困難。報端上開始出現許多對大學聯招新制度的懷疑，提醒在某些狀況下，新制分發會出問題。
無論如何，一年一年過去了，新鮮人也一年一年進了大學。民國82年，財團法人大學入學考試中心成立， 83年起，大學聯考電算作業改由逢甲大學電算中心接手；後來，可能是因為地緣關係，希望行政作業與電算作業能配合得好，因此選擇了台大為合作伙伴，於是，自民國85年起，大考電算作業就改由台大電算中心接手。
筆者當時任職於台大電算中心程式設計組，有幸參與此工作，撰寫分發程式，因此對分發的細節有較多的瞭解，且此程式至今仍繼續使用（當然每年會依實際狀況做些修改）。本文打算以分發程式為討論的重心，探討分發的技術問題及其衍生的耐人尋味的問題。因為筆者全程參與85年大學聯考電算作業的整個過程，因此本文將以85年的大學聯考做為主要討論對象，並簡要提及85年之後的改變。
2 大學聯考電算作業概述
大學聯考是個龐大的作業，且必須戰戰兢兢，全力以赴。作業大致分為行政作業以及電算作業。其中，電算作業可以簡單地將之分為5大部分：
(1) 基本資料建立：包括考生基本資料輸入、基本資料異動處理、應考人員清冊、試場分配表、考場座位表...等。
(2) 電腦閱卷：主要是選擇題電腦閱卷。
(3) 計分、成績單、相關統計：包括電腦閱卷資料與人工閱卷資料併檔、計算學科/術科總分、列印成績單、統計各科高低標、考生總分排名表...等。
(4) 分發：主要是讀入志願資料、分發。
(5) 放榜：主要是列印錄取名單（小字榜/大字榜）、各校系最低錄取標準檔、校系錄取人數資料、錄取校系代碼表...等。
3 分發程式探討
這裡討論的主題是：要怎麼分發？簡單來說，分發不外是將一個考生指定到某一系，或是某一系要收哪些學生。這兩個答案看似一體兩面，但在意義上，還是有差別的。
讓我們先來討論演算法中穩定婚姻問題(Stable
Marriage Problem)，假設有一家婚友中心，要將報名參加的各五名適婚年齡男女配對，若是任意配對，會有5!=120種情形，亂點鴛鴦譜極可能產生怨偶，我們應該根據他們的意願去撮合才對。首先，要求男生（以A、B、C、D、E表示）及女生（以1、2、3、4、5表示）各將對方在自己心目中的排名列出來，假設排出來的順序如下表所示：
|
A |
B |
C |
D |
E |
|
1 |
2 |
3 |
4 |
5 |
|
2(4) |
1(4) |
2(5) |
1(3) |
5(4) |
|
E(4) |
D(3) |
A(4) |
C(4) |
D(5) |
|
5(5) |
2(3) |
3(4) |
3(2) |
3(5) |
|
A(3) |
E(3) |
D(2) |
B(4) |
B(5) |
|
1(2) |
3(3) |
5(3) |
2(1) |
2(2) |
|
D(1) |
B(2) |
B(3) |
D(4) |
C(3) |
|
3(1) |
4(2) |
4(1) |
4(3) |
1(1) |
|
B(1) |
A(1) |
C(2) |
A(5) |
E(1) |
|
4(4) |
5(2) |
1(5) |
5(1) |
4(5) |
|
C(5) |
C(1) |
E(2) |
E(5) |
A(2) |
刮號中的數字為喜歡的順序，如A欄之下的2(4)表示A是2的第四順位人選。
我們希望產生穩定配對，例如(A,1)、(B,2)、(C,3) 、(D,4) 、(E,5)的配對是不穩定的，以(C,3) 、(D,4)兩對而言，3比較喜歡D（與C相比），4又比較此歡C（與D相比），所以結婚後，這兩對成為怨偶，3、4可能離婚再嫁互換丈夫，所以這是不穩定的配對。
如何找出穩定配對？若以男生為主，我們先假設讓他與他最喜歡的女生配對（箭頭上面的數字表示步驟的順序）：
A 
B 
C 
顯然，第三步驟出了衝突，A和C都最喜歡2，怎麼辦？這時候就徵詢2的意見，由上表得知A與C相比，2比較喜歡A，所以C只好退而求其次，選擇3。照這原則下去直到完成配對工作：
A 
B 
C 
D 
E 
經過了15個步驟，我們得到的配對結果是(A,1)、(B,4)、(C,5)、(D,3)、(E,2)，雖然沒有人是「第一志願」，至少這是穩定的，因為他比較喜歡卻嫁給別人的那位女生，並沒有比較喜歡他，不會因為他而離婚再嫁。穩定的配對是「雖不滿意但可接受」，且是無法抱怨的。
如果用女生的意願來排，會得到相同的結果嗎？
1 
2 
3 
4 
5 
結果只花了6個步驟就得到不一樣的配對結果：(A,3)、(B,5)、(C,4)、(D,2)、(E,1)。從這裡，我們可以知道，穩定婚姻問題並非只有唯一解，但是，我們以其中一方（男生或女生）為主，會得到唯一解。
回到分發的正題，我們再舉一個例子來說明，假設有甲、乙兩名考生參加聯考，考試科目有英、數兩科，有兩個系參加聯招，分別是A系和B系，A系強調英文，所以英文分數加重50%，B系強調數學，因此數學分數加重50%，且每系各錄取一名。假設考試成績及考生所填寫的志願如下表所示：
|
|
英文 |
數學 |
總分 |
|
|
志願一 |
志願二 |
|
甲 |
80 |
70 |
150 |
|
甲 |
B |
A |
|
乙 |
70 |
80 |
150 |
|
乙 |
A |
B |
接著我們要根據他們的成績和志願來分發，請看下表：
|
A |
B |
|
甲(190,2) |
乙(190,2) |
|
乙(185,1) |
甲(185,1) |
對A系來說，甲的分數比較高，對B系來說，乙的分數較高。所以，若以系的立場，A要選甲，B要選乙，最低錄取總分（加重後）都是190分，甲、乙兩人都是以第二志願進去，雖然甲想要進第一志願B系，但是他的分數(185分)比乙的190分還低，只好認命，乙也是同樣的情形，他們都無法抱怨此結果。不過，若照我們之前討論的，以考生為主，則可得：
甲 
乙 
這個方法雖然讓甲、乙兩位考生都以第一志願進了他們所想要的科系，但是，A、B兩系的最低錄取標準都降到了185分。
這裡就牽涉到聯考的基本精神：分發應該以考生的意願為主，而非科系的意願。所以上例中，應以第二種方式來分發。
雖然兩個問題不完全相同，但在觀念上是類似的。分發問題，可以想成是做多（考生）對一（科系）的穩定配對，方法則可利用回溯法(Backtracking)。
4 分發程式的演算法
根據上節的說明，我們利用回溯法，將分發程式的演算法寫出：
(起始部分)