程式解題的學習

程式解題的學習資料結構演算法線上程式解題系統ACM UVA POJ GCJ Online Judge. Home ArticleSeries _Architecture __PatternsofEnterpriseApplicationArchitecture __Refactoring:ImprovingtheDesignofExistingCode _ASP.NET Home About Home程式解題程式解題的學習 程式解題的學習 CodeParadise June16,2014 真的畢業了!找到適當的BLOG可以寫東西啦~~~就是GOOGLE的BLOGGER!有好多Plugin可以用、template可以自己設定,在沒有網頁空間下,覺得這蠻不錯的. 此篇是參考NPSC補完計畫，結合其內容與我的種種解題的學習過程與方法～ 身邊的同學或學弟妹常會問如何學程式、提高程式設計能力或者如何解題。

　　我不是像中央MORRIS、清大楊易霖、台大以及其他各種怪物等國手， 但是在這多年來解題的過程有許多說不完的心得與想法， 在此分享給想挑戰程式設計比賽的人， 當作一個學習途徑的參考。

　　以下內容是以程式解題方向為主的學習過程與方法，無法涵蓋所有程式設計的學習方法，但我想共通點是一樣的。

1.　先熟練C/C++或JAVA基本語法： 　　找一本你覺得看起來最舒服的書， 不要說去找什麼很有名的聖經本之類的， 除非底子已經很好，可以再來研讀有深度的書。

最最最最最基本的是需要以下（很重要所以強調）： 懂標準輸入輸出、變數宣告、 if-else、switch、while(do-while)、for等流程控制語法、 陣列、字串、struct的使用（C/C++）、class的使用(JAVA、c++） 以及簡單的排序法。

進階一點就再學自定函數、遞迴函數等， 這階段主要是學習程式的語法， 讓你的想法可以很快地化成程式碼， 不用馬上說想寫很困難的程式。

2.進入線上程式解題系統練習 學程式絕對不只是要用"看"的就能學會， 學程式絕對不只是要用"看"的就能學會， 學程式絕對不只是要用"看"的就能學會， 學程式絕對不只是要用"看"的就能學會， 學程式絕對不只是要用"看"的就能學會， （很重要所以我寫五行） 　　有些重要課程只有講理論而沒實際操刀寫程式，實在是無法深刻了解其中的奧妙而無法成長，特別是遇到需要debug的技巧是書上不會教的！ 因為沒有人會有那個耐心幫你檢查所有的程式是不是有bug， 所以找一個可以自動Judge的系統是很重要的～ 新手的話，推薦兩個平台 第一個：「高中生程式解題系統」 http://zerojudge.tw/ 　　歷史非常悠久的台灣中文解題系統，是由高雄師範大學經營，裡面的題庫大都是中文，也是高中職學生常用的解題訓練平台，許多TOI、IOI國手大都在這起步。

可惜題目並沒有做難易度分類，即使在基礎題庫的題目也有很難的，需要有人指導會比較清楚。

第二個：「ITSA的E-TUTOR」 http://e-tutor.itsa.org.tw/e-Tutor/ 　　近年來新的中文解題系統，網站上有中英文的題目，每種題目又有分各類型的題目， 更是有做難易度的區隔，讓學解題的使用者有個清楚的方向。

可惜這平台缺點是常有題目的敘述不完整，比如輸入測資的範圍沒說明等， 會給使用者額外的困擾。

3.開始學習資料結構、演算法 　　基本題解到一個程度，會發現學的東西不夠用， 這時候就要進入下一個階段, 開始學習資料結構和演算法了。

　　這部分一樣是去書店找一本你看得順眼的書, 以我個人而言，在資料結構的部分，除了有原文聖經本 EllisHorowitz寫的FundamentalsofDataStructuresinC(或C++) 我有另外買蔡明志的「資料結構--使用C++(也有C++、JAVA版)」 另外有網友推薦胡昭民的「圖解資料結構」 選一本即可，主要是看懂資料結構的觀念, 書裡程式碼希望是能研讀，最好是實作。

而有些樹的章節裡面,只要看到二元樹(包括二元搜尋樹、Heap)就夠了, 後面AVL-Tree、2-3-4Tree、B-Tree等可以不用看，基本上解題不會用到。

　　演算法的書,之前我上課原文書是用　AnanyV.Levitin寫的IntroductiontotheDesign& Analysisof Algorithms，而中文書推薦蔡宗翰的「演算法：使用C++虛擬碼」，這本的內容讓我學到很多。

解題的程式最常會用的演算法包含各個擊破法 （Divide-and-Conquer）、動態規劃(DynamicProgramming)、貪婪演算法(Greedy)、 回溯(Backtracking)、分支界限法(Branch-and-Bound)等，有時解題遇到的問題可以用很多種演算法解。

資料結構與演算法的書讀完後，還不足的可以到「演算法筆記」挖資料http://www.csie.ntnu.edu.tw/~u91029/ 這網站陪我好幾年，也有我幫站長debug文章的痕跡，可惜現在終止營運，有點可惜～ 演算法聖經本是MIT教授Cormen寫的IntroductiontoAlgorithms，以台清交成資訊工程學生以及國手，幾乎都看這本學起，書的內容講的很完整，說是聖經本不為過，真的要讀可以啃這本，但不建議讀中文翻譯本，翻譯的很爛。

4.使用進階的線上程式解題系統 　　第二段提到高中生程式解題系統(ZeroJudge)、E-TUTOR 雖然裡面部分題目比較簡單，可以很容易建立自信心、學習基本解題方法。

但到達某一程度後，有些題目會很難、甚至學習成長的幫助不大，此時可以改到其他網站練習。

　　首先最推薦的就是最多人用過，俗稱ACM的UVaOnlineJudge, http://uva.onlinejudge.org/ 而「Lucky貓的ACM園地」有提供一些題目的中譯還有難易度分級, http://luckycat.kshs.kh.edu.tw/ 可以搭配使用。

當然是希望能看原文直接解題是最好，畢竟國際解題全都是用英文出題。

　　第 二個是Uhunt，這不是新的解題系統，而是UVa的實況系統，是由新加坡大學的解題團隊所建立的網站，提供現在全世界有哪些人在解題、解題狀況如何、排 名如何、程式執行時間多長，對我而言是個很刺激的網站，且長久下來會看見一些很奇怪的熟ID。

而uhunt上中間有一個Competitive ProgrammingExercises，是新加坡解題團隊所分類的題目，有分好題目類型與難易度，也是提供使用者很完整的解題方向。

5.進階解題書籍 　　前面提的資料結構與演算法書籍，只是＂基礎知識＂而已，有時學完後還是無法對某些題目想出方法，此時推薦幾本書籍。

第一是劉汝佳撰寫的「算法竞赛入门经典」跟「算法竞赛入门经典——训练指南」 ， 在台灣去年有代理出繁體版，名稱分別為《提升程式設計的邏輯思考力─國際程式設計競賽之演算法原理、題型、解題技巧與重點解析》與《提升程式設計的解題思 考力─國際演算法程式設計競賽訓練指南》。

這兩本書而言，初學者先讀「算法竞赛入门经典」，讀完後再來讀「算法竞赛入门经典——训练指南」。

書的內容就是 專門講解如何將基本的資料結構與演算法知識來解決程式解題的題目。

以Uva而言，題目是變化多端，有些題目若沒有人指導確實很難自己想出來，而這些書提供 很多整合資料結構與演算法的概念，提升解題者的思路。

另外一題，劉汝佳起初是中國的解題國手，現任中國專業解題教練與ACM-ICPC命題委員，中國資訊學生幾乎都聽過他名字。

他寫了這些書更是帶動中國的解題氣氛，每年上海交通大學幾乎都會進到ACM-ICPC決賽的前幾名，真的是很恐怖。

第二本是日本國手寫的プログラミングコンテストチャレンジブック，台灣也有代理成翻譯書，叫做《培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享》，也是跟劉汝佳寫得差不多，只是這本書是拿POJ跟GCJ的題目來講解。

6.學海無涯 　　以解題而言，初學者最容易犯的錯，以為只看書就懂什麼叫做資料結構或演算法，甚至只挑簡單題來做，這樣是永遠不會成長。

以我個人而言，大學的資料結構與演算 法都是有寫程式作業，且佔總成績很重，不寫好就是等著被當掉，因此有很多時間花在學好資料結構與演算法的理論與程式設計。

從大二開始就跟著學長姐進入解題 比賽這一條不歸路（？），起初真的如同前面提到，即使課程學過資料結構與演算法的基礎知識，卻還是不會轉換成解題的方法，意思就是解題寫太少，且又碰得太 簡單，才沒有進步。

之後到了大三，大概也才解了一百多題Uva題目，但覺得學的還是少。

直到轉學至長榮，突然有個發神經的動力，開始瘋狂解題，真正體會到 資料結構與演算法的實作能力與奧妙之處，短短一年多解了４百題，這趟過程雖然辛苦，但是卻非常值得！ 　　從以前去中山、成大的全國大專程式競 賽、南區程式競賽等比賽，常常看見很熟悉的成大選手臉孔，直到現在遇到的同一輩與新一代的強選手，這趟比賽過程值得回憶。

最後今年的ITSA桂冠賽仍沒獲 獎，但也還是值得了，至少跟成大同解數還蠻高興(?)。

而CPE(大學程式能力檢定)在上禮拜二拿下A+的成績，也是了無遺憾！ 　　希望這篇文章有能幫助到有共同志趣在解題上的人，更希望能帶動程式解題氣氛，解題只有好處沒壞處，也如演算法筆記所述，解題能學到以下這五種能力： 　　一、智力思考：藉由智力測驗問題、益智遊戲（如數獨、孔明棋、倉庫番）、數學科普書等等，可以活絡大腦思路，培養觀察問題與分析問題的能力。

　　二、數學：從學校教科書可以學到很多數學概念、數學方法、甚至是數學公式，套用在問題上面來解決問題。

　　三、計算學：從學校教科書和網路上的資源，可以學到很多計算方法，套用在問題上面來解決問題。

　　四、程式語言：從程式語言的書籍（C++Primer、EffectiveC++、程式設計師的自我修養）、計算機概論等書中學習。

　　五、程式設計：從opensource與其他人寫的程式碼中學習一些寫程式的原則以及漂亮的寫法。

所以，解題Z>B是百分百正確的! 7.疑問 　　也有人會問，做解題那麼多對實際撰寫專題（系統）有用嗎？這要回答「部分有用」，畢竟一個系統就是要解決一大堆問題集合的工程方法，而解題只有解一部分小問 題。

但是學過演算法會知道，要想辦法把問題切成子問題來解決，做系統也一樣，每一個系統可以切成各種功能的子系統，每一子系統是針對特定問題作解決的方 案。

因此一個子系統的功能完整，正是一個（數個）程式的執行能力，而程式又如一位Niklaus Wirth大師所說：「程式　＝　演算法＋資料結構」。

好得程式可以整合出一個好的系統，這是我個人對系統實作的觀念，所以解題學的好，仍然對做系統有幫 助。

只是有些是解題學不到的，比如如何使用API來做完成一個子系統的功能，必須要有閱讀文件的能力，解題上沒有閱讀文件的學習方法。

--------2014/6/16補充--------- 　　這陣子接觸到2048bot大賽，在這過程學到何謂對抗搜尋的branch-and-bound演算法，包含minimax、alpha-betaprune、expectimax、negascout等方法。

目前ACM題目的解題我還沒遇到剪枝的題目，藉由這2048比賽的機會，學到了剪枝的精神！只是國內研究單位太強了，交大的居然能十幾%的16384Tile....超好奇他們演算法能快狠準到此成績。

Tags ACM 程式解題 Facebook Twitter PostaComment 7 Comments Unknownsaid… 優質文章推推推推推 June16,2014at4:45PM CodeParadisesaid… 謝謝指教 June16,2014at4:51PM 2AXSsaid… 未看先推 June16,2014at4:54PM Unknownsaid… 疑是從FB移植的好文=) June16,2014at4:58PM CodeParadisesaid… ^.< June16,2014at5:00PM CodeParadisesaid… 謝謝呀>.