☆☆☆☆☆
簡體網頁||繁體網頁



點擊這裡下載

類似圖書 點擊查看全場最低價

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

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

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

作者簡介

林盈達

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

黃世昆

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

楊昌彪

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

葉正聖

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

謝育平

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

第一章  程式能力檢定簡介
第二章  程式能力檢定評審係統
第三章  瘋狂程設軟體
第四章  C/C++基本輸入與輸齣
第五章  由基礎至進階
第六章  一顆星題解
第七章  二顆星題解
第八章  三顆星題解

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所示。中間的部分代錶所有送齣的程式碼被綫上評審伺服器認可為正確的比例。由於綫上評審伺服器可隨時評審程式碼，故使用者對於尚未被評審認可的程式碼可以再次遞送，直到正確為止。圖的最右側代錶該題最後遞送齣正確程式碼的使用者比例。

所有ACM ICPC題目均有固定格式，每題包含General Description（一般描述）、Input Format（輸入格式）、Output Format（輸齣格式）、Sample Input（輸入範例）、Sample Output（輸齣範例）共五大部分。每題長度大約一至三頁左右。圖1.2為題目範例。

雖然收錄於UVa網站的ACM ICPC題目庫，對於每一題均有遞送正確程式碼的百分比，以及正確解題的使用者百分比，但仍不足以完全分辨其難易程度。我們為瞭讓學習者可以瞭解適閤練習的題目，並讓教師可以配閤授課課程內容做為學生之實作或測驗題目，乃將題目區分為五個等級，如下所示：

• 一顆星(level 1)：學習完計算機概論之後即可解答（專傢級設計師大約可於10分鍾撰寫完畢）。
• 兩顆星(level 2)：學習完資料結構之後纔能解答或是苦工題（專傢級設計師大約可於10至30分鍾撰寫完畢）。
• 三顆星(level 3)：需良好的演算法或數學方法纔能解答（專傢級設計師大約可於30至100分鍾撰寫完畢）。
• 四顆星(level 4)：需要特殊的演算法或是綜閤多種演算法纔能解答（專傢級設計師需要超過100分鍾纔能撰寫完畢）。
• 五顆星(level 5)：超越四顆星的極特殊題目。

1.3 大學程式能力檢定(CPE)
「ACM亞洲區颱灣賽區大專程式設計競賽」自1995年起，每年在颱灣各大學輪流舉行。為瞭提升國內大學生的程式設計能力，各大學相關科係的教授於2008年組織瞭「國際計算機器協會程式競賽颱灣協會」（ACM-ICPC Contest Council for Taiwan，簡稱ACM-ICPC Taiwan Council），做為跨校交流與閤作的平颱。該協會下設三個委員會如下：

1. 推動委員會：負責資源與庶務之整閤，原則上由參與學校之計算機中心（或等同單位）主任或資訊係係主任組成。

2. 技術委員會：由教練與命題老師組成，負責培訓與命題事務，原則上成員須具備程式培訓與命題之能力與經驗。

3. 大學程式能力檢定委員會（Collegiate Programming Examination Committee，簡稱CPE Committee）：共同舉辦CPE程式檢定考試，由已參與及即將參與舉辦CPE檢定考試之學校代錶參加，該學校代錶原則上為該校考場負責人。

大學程式能力檢定（Collegiate Programming Examination，簡稱CPE）旨在提升全颱灣學生的程式設計能力，由學生透過綫上程式設計，利用電腦自動評判，以檢測程式設計能力。CPE每年辦理四次，大約為每年的3、6、9、12月。CPE採電腦現場上機考試，以電腦自動評判，並由各校派員監考。考試時，會封閉與考試無關的網路。考生除紙本字典外，不能攜帶任何資料。考生若為大專學生，可免費報名。CPE的標誌如圖1.3所示。

None

大學程式能力檢定：CPE祕笈 電子書 下載 mobi epub pdf txt 2025

類似圖書 點擊查看全場最低價

查看全網最低價