好康資訊優惠

CHAPTER1程式能力檢定簡介

1.1 ACM國際大學程式競賽





ACM ICPC（International Collegiate Programming Contest，國際大學程式競賽）是由 ACM（Association for Computing Machinery，國際計算機器協會）主辦的一年一次程式設計競賽。藉由競賽方式來展現大學生創新能力、團隊精神，以及在壓力下編寫程式、分析和解決問題的能力。自從1970年代開創以來，經過三十多年的發展，ACM ICPC已成為全球電腦界中歷史最悠久且最具影響力的程式競賽。以2011至2012年為例，參加各地區域賽的隊伍超過8000隊，涵蓋88個國家及超過2000所大學。區域賽優勝隊伍會再集中於一處參與世界總決賽的競逐。以下列舉ACM ICPC的重要里程碑：





? 1970年：美國Texas A&M University大學程式設計比賽。



? 1977年：第一次舉辦世界總決賽。



? 1977至1989年：參與比賽的大學主要來自美國與加拿大。



? 1989年：建立區域賽(regional)制度，優勝隊伍才能參加世界總決賽。



? 1991年：亞洲首支隊伍（台灣交通大學）參加世界總決賽。



? 1995年：首度舉辦亞洲區域，並在台灣舉行，由國立政治大學辦理。



? 1996年以前：歷年贊助廠商依序為Apple、AT&T和Microsoft。



? 1997年之後：IBM公司為此競賽的主要贊助商。



? 1997年：參賽隊伍1100隊，來自560個大學。總決賽地點在美國聖荷西，代表台灣的台灣大學榮獲總決賽第4名，這是台灣隊伍首次進入前十名。



? 2002年：中國的隊伍首度獲得總決賽冠軍——上海交通大學。



? 2010年：參賽隊伍7900隊，台灣的隊伍獲得有史以來最好的成績，為總決賽第三名——台灣大學。



? 2011年：世界總決賽原訂於埃及沙姆沙伊赫舉行，但由於埃及當時發生暴動，因而將總決賽地點更換為美國奧蘭多。





自1997年以來的參賽隊伍數量與冠軍隊伍，詳列於表1.1。



表1.2、表1.3與表1.4分別列出2010年、2011年與2012年世界總決賽排名較為前面的隊伍。2010年前13名的隊伍，俄羅斯與中國合計佔了9個；2011年前12名的隊伍，俄羅斯與中國合計佔了7個；2012年前12名的隊伍，俄羅斯與中國合計佔了6個。由此可以看出世界頂尖的優秀隊伍超過半數集中於俄羅斯與中國，代表這兩個國家對於程式設計的能力非常重視。





1.2 ACM ICPC題目庫



ACM ICPC舉行三十餘年，所累積的寶貴資源，就是歷次的比賽題目。有些題目已經收錄於UVa線上評審網站（UVa online judge，網址為http://uva.onlinejudge.org/，其中UVa乃指西班牙瓦拉多利大學(Universidad de Valladolid)），目前累積已經超過3600題。全世界各地有許多人士在其上註冊帳號，進行練習，以提升程式設計能力。





該網站也會列出各題被解決的情形，以便讓人區分難易程度，如圖 1.1所示。中間的部分代表所有送出的程式碼被線上評審伺服器認可為正確的比例。由於線上評審伺服器可隨時評審程式碼，故使用者對於尚未被評審認可的程式碼可以再次遞送，直...