大學程式能力檢定：CPE祕笈

　　本教材設計包含三個面向：系統、基礎、題解。在系統方面，我們在第一章介紹ACM-ICPC及CPE的發展與規則；第二章介紹CPE線上(on-line)練習與現場(on-site)考試的系統與機制；第三章介紹一個本機端的練習軟體——瘋狂程設，它透過測資腳本與批改腳本讓學生在練習中減少語法、語意與邏輯的錯誤，也透過短碼競賽讓學生能更精簡地撰寫程式。

　　在基礎方面，第四章介紹C與C++輸入輸出的函式與格式，減少初學學生因為程式輸出輸入問題造成上傳程式錯誤的可能；第五章有系統地講解解題技能，從理解題意到挑選合適的演算法（包括排序、搜尋、貪心(greedy)、動態規劃、圖形走訪、最小生成樹、最短路徑、最大流等常用演算法）不一而足，同時考量程式執行時間與記憶體用量，並交代如何設計測資以在上傳程式前檢驗程式的正確性；最後提醒要善用既有資源，利用函式庫來設計解題所需的功能，以減少撰寫程式的時間。

　　在題解方面，我們依據難易等級提供三章共84題之題解，另有8題用在前面章節中做為例子。第六章至第八章分別是一顆星至三顆星題目之題解，除了區分難易度，再依據題型分節，其中包含字元與字串、數學計算、大數運算、幾何、排序、圖論、模擬、動態規劃等。讀者可以透過本書進入程式設計之門，並培養精進解題與程式的實力。

作者簡介

林盈達

　　現職：國立交通大學資訊工程學系教授
　　學歷：UCLA電腦科學博士
　　專長領域：網路協定設計、實作、分析與測試；網路安全、無線通訊及嵌入式軟硬體效能

黃世昆

　　現職：國立交通大學資訊技術服務中心副主任
　　學歷：交通大學資訊工程博士
　　專長領域：軟體自動測試研究、軟體安全、自動攻擊產生器(CRAX)

楊昌彪

　　現職：國立中山大學資訊工程學系教授兼系主任
　　學歷：清華大學資訊科學博士
　　專長領域：演算法及其延伸應用；字串、檔案相似度比對相關演算法之設計與分析

葉正聖

　　現職：銘傳大學資訊傳播工程系助理教授
　　學歷：臺灣大學資訊工程博士
　　專長領域：電腦圖學、虛擬實境、電腦視覺及互動技術

謝育平

　　現職：銘傳大學資訊工程學系助理教授
　　學歷：臺灣大學資訊工程博士
　　專長領域：計算組合學、網路路由技術、數位典藏、圖書館自動化、光學文字辨識與課程自動化

序

拔擢頂尖vs.提升平均

　　由於ACM-ICPC亞洲區黃金雄主任（美國德州大學教授）的鼓勵與協助，「國際計算機器協會程式競賽台灣協會」(ACM ICPC Contest Council for Taiwan) 於2008年成立。成立之初，協會的思考重點都在如何拔擢頂尖，讓更多的頂尖學生參加ACM-ICPC區賽(Regional Contest)及總決賽(World Final)。但我們很快地發現，拔尖只關注大約前5%的少數學生，大部分學生對這些國際競賽幾乎沒有投入甚或注意。根據我們的觀察，由於程式作業抄襲或修改容易，約四分之一的資訊系學生不太會寫程式（各校比率略有差異），四分之三的學生程式寫得不夠多（除了修課作業與專題要求之外不寫程式），未來會選擇從事程式設計的學生不到二分之一，其他傾向轉而投入不太需要撰寫程式的工作。這種「生態」當然影響了國家資通訊產業設計產品的「產能」，而產業界對於大學生的程式設計訓練不夠紮實也是抱怨聲不斷。因為這導致他們在徵聘新人時，必須透過自己設計的程式測驗才能挑選出適合的人才。

　　許多大學教授因有研究論文發表的壓力，對於研究生的研究要求，著重於創新設計與理論分析的突破，而較少要求系統實作之苦工。他們因為專心致力於研究，而無暇顧及基礎的程式教學訓練。有心於大學部程式訓練課程的教授，單憑一己之力也很難改變整個生態。

　　上述的情形讓協會開始在拔尖之餘，開始省思如何提升整體平均。思考的大方向是將ACM-ICPC國際賽的題庫拿來做為標準測驗的題目，然後推廣至各校共同辦理測驗，並且採認於大學部畢業要件與研究所入學參考。因為ACM-ICPC國際賽的題目都經過歷練，有相當的品質與水準，所以不需要擔心題目品質的問題；也因為題庫夠大（目前已經超過3600題，並且陸續增加中），所以也不需要擔心學生可能做過我們所挑選的題目。如果學生做過題目而且在考試時也可以寫得出程式，其程式能力必定也相當不錯，畢竟程式設計需要理解與邏輯思考，無法單靠死背。有了題目品質的保證後，我們設計了「大學程式能力檢定」 (Collegiate Programming Examination, CPE) 做為考試的形式與機制，希望透過CPE及各校的共同參與來改變上述的生態，藉此提高台灣資訊產業的產能與競爭力，並增加參加國際競賽的可能人口。

　　CPE配方：多校、千人、同步、遠距、同一份題目之程式能力檢定

　　CPE具有獨特的配方，而有別於現有的競賽與檢定系統，例如ACM-ICPC區賽與總決賽使用單一實體場地最多100隊同時競賽，或電腦技能檢定在電腦教室隨時有人考試，而考題由遠端的伺服器隨機抽取。上述兩種實體場地或遠端題庫的模式都無法滿足千人同時考試的目標，必須結合兩者才能達到。所以「CPE的配方」是多校、千人、同步、遠距、同一份題目；多校的場地才能免除舟車勞頓，又能達到千人的規模，而遠距題庫能支援各校同步舉辦來考同一份題目。

　　由於CPE是一項檢定考試，監考、防弊與系統穩定度非常重要。學生在各校的電腦教室考試，用戶端的電腦軟體必須確保學生無法連線到非CPE伺服器以外的地方，而CPE係透過虛擬主機的機制達到這項限制。此外，各校考場需避免學生在現場交談作弊，甚或冒名考試，所以電腦教室要有專人監考。伺服器端除了支援多校千人同步存取題目，以及自動評審學生上傳的程式之外，還要克服系統延展性與穩定性的問題。目前CPE系統架構有多台前端與後端伺服器，可兼具支援大量考生及達到伺服器穩定備援的目的。

　　前述提到，題目是由ACM-ICPC區賽與總決賽比賽過而收錄於UVA題庫，品質沒有問題，可以避免多年前資訊教育界推動TGRE因題庫品質問題，造成考試成績鑑別力不足的情形。但是，UVA題庫並沒有公布上傳程式的測試資料（簡稱測資），所以CPE在挑選題目時必須自行準備測資。另外，ACM-ICPC區賽與總決賽進行五小時，三人組成一個隊伍，題目大約在8至10題左右。相較之下，CPE是個人考試檢定，進行三小時，題目有7題，除了時間較短且題目較少外，選擇的題目也朝向簡單化。在一至五顆星難易等級中，ACM-ICPC國際賽一顆星與兩顆星大約各只有一題，其餘題目都是三顆星以上；而CPE一顆星有三題，二顆星有二題，三顆星以上有二題。

　　CPE現況

　　CPE自2010年6月第一次由中山大學與交通大學合辦開始，每季舉辦一次，時間為平日18:00至21:40（包含考前練習）。截至2012年12月已舉辦十次，參與協辦的學校數由2、6、9、19、17、21、25、30校成長到約40校，參加檢定考試的學生數也成長到將近1000人。2011年至2013年由中山大學主辦（選題與測資準備、統籌相關行政事務與對外宣傳），交通大學負責技術支援（伺服器維護），其他學校參與協辦（考場準備與監考）。CPE也提供學生申請中英文成績單，其中會顯示絕對成績（總題數7題、答對題數、成績等級）及相對成績（參加學生數、排名）。由於考試人數夠多、題目具有鑑別力，所以這份成績單具有相當的可信度。程式能力不好的學生，可能一題也解不出來；能解四題的學生，程式能力已是相當優秀；而一次解出兩題是許多大學設定的及格標準。

　　CPE的推行，需要舉辦與採認同時並進，如果沒有學校採認，空有許多學校舉辦，並無法吸引夠多的學生來考試。目前已有多所大學將CPE設定為：(1)大學部之畢業要件（單次考試答對兩題或多次考試累積答對三題或四題）；(2)碩士班甄試入學之參考資料（列入申請表、推薦信或招生簡章）；(3)在課程上使用當作期中期末上機考試的方式。

　　教材設計：系統、基礎、題解

　　儘管有不少線上資源可以讓學生了解ACM-ICPC、UVA、CPE，但仍欠缺一本整合各種資訊的書籍，學生及教師都會需要一本CPE入門的書，讓學生可以準備檢定考試，也讓教師能善加利用CPE於課程、入學與畢業。本教材設計包含三個面向：系統、基礎、題解。在系統方面，我們在第一章介紹ACM-ICPC及CPE的發展與規則；第二章介紹CPE線上(on-line)練習與現場(on-site)考試的系統與機制；第三章介紹一個本機端的練習軟體——瘋狂程設，它透過測資腳本與批改腳本讓學生在練習中減少語法、語意與邏輯的錯誤，也透過短碼競賽讓學生能更精簡地撰寫程式。

　　在基礎方面，第四章介紹C與C++輸入輸出的函式與格式，減少初學者因為程式輸出輸入問題造成上傳程式錯誤的可能；第五章有系統地講解解題技能，從理解題意到挑選合適的演算法（包括排序、搜尋、貪心(greedy)、動態規劃、圖形走訪、最小生成樹、最短路徑、最大流等常用演算法）不一而足，同時考量程式執行時間與記憶體用量，並交代如何設計測資以在上傳程式前檢驗程式的正確性；最後提醒要善用既有資源，利用函式庫來設計解題所需的功能，以減少撰寫程式的時間。

　　在題解方面，我們依據難易等級提供三章共84題之題解，另有8題用在前面章節中做為例子。第六章至第八章分別是一顆星至三顆星題目之題解，除了區分難易度，更依據題型分節，其中包含字元與字串、數學計算、大數運算、幾何、排序、圖論、模擬、動態規劃等。我們希望讀者可以透過本書進入程式設計之門，並培養精進解題與程式的實力。

　　本書特點
　　多校、千人、同步、遠距、同一份考題之大學程式能力檢定(CPE: Collegiate Programming Examination)之入門教材。
　　學生只需具備C或C++基礎程式能力即可上手。
　　線上練習系統與現場考試系統之介紹。
　　基礎輸入輸出與進階解題技能之講解。
　　ACM-ICPC UVA題庫中精選92題題目之題解。
　　依難易度蒐集各類題型：字元與字串、數學計算、大數運算、幾何、排序、圖論、模擬、動態規劃等。
　　每一題解包含UVA/CPE編號、題意、解法、程式碼及程式碼註解。