實用演算法分析與程序設計

㈠ 參加ACM競賽需要用的參考書

ACM國際大學生程序設計競賽：知識與入門.pdf

鏈接: https://pan..com/s/19OY2FJUkk4RhW5WTsPkwfQ

《ACM國際大學生程序設計競賽:知識與入門》適用於參加ACM國際大學生程序設計競賽的本科生和研究生，對參加青少年信息學奧林匹克競賽的中學生也很有指導價值。

㈡ acm初學者要准備什麼 看什麼書啊

剛剛接觸信息學領域的同學往往存在很多困惑，不知道從何入手學習，在這篇文章里，我希望能將自己不多的經驗與大家分享，希望對各位有所幫助。
一、語言是最重要的基本功

無論側重於什麼方面，只要是通過計算機程序去最終實現的競賽，語言都是大家要過的第一道關。亞洲賽區的比賽支持的語言包括C/C++與JAVA。筆者首先說說JAVA，眾所周知，作為面向對象的王牌語言，JAVA在大型工程的組織與安全性方面有著自己獨特的優勢，但是對於信息學比賽的具體場合，JAVA則顯得不那麼合適，它對於輸入輸出流的操作相比於C++要繁雜很多，更為重要的是JAVA程序的運行速度要比C++慢10倍以上，而競賽中對於JAVA程序的運行時限卻往往得不到同等比例的放寬，這無疑對演算法設計提出了更高的要求，是相當不利的。其實，筆者並不主張大家在這種場合過多地運用面向對象的程序設計思維，因為對於小程序來說這不旦需要花費更多的時間去編寫代碼，也會降低程序的執行效率。

接著說C和C++。許多現在參加講座的同學還在上大一，C的基礎知識剛剛學完，還沒有接觸過C++，其實在賽場上使用純C的選手還是大有人在的，它們主要是看重了純C在效率上的優勢，所以這部分同學如果時間有限，並不需要急著去學習新的語言，只要提高了自己在演算法設計上的造詣，純C一樣能發揮巨大的威力。

而C++相對於C，在輸入輸出流上的封裝大大方便了我們的操作，同時降低了出錯的可能性，並且能夠很好地實現標准流與文件流的切換，方便了調試的工作。如果有些同學比較在意這點，可以嘗試C和C++的混編，畢竟僅僅學習C++的流操作還是不花什麼時間的。

C++的另一個支持來源於標准模版庫（STL），庫中提供的對於基本數據結構的統一介面操作和基本演算法的實現可以縮減我們編寫代碼的長度，這可以節省一些時間。但是，與此相對的，使用STL要在效率上做出一些犧牲，對於輸入規模很大的題目，有時候必須放棄STL，這意味著我們不能存在「有了STL就可以不去管基本演算法的實現」的想法；另外，熟練和恰當地使用STL必須經過一定時間的積累，准確地了解各種操作的時間復雜度，切忌對STL中不熟悉的部分濫用，因為這其中蘊涵著許多初學者不易發現的陷阱。

通過以上的分析，我們可以看出僅就信息學競賽而言，對語言的掌握並不要求十分全面，但是對於經常用到的部分，必須十分熟練，不允許有半點不清楚的地方，下面我舉個真實的例子來說明這個道理——即使是一點很細微的語言障礙，都有可能釀成錯誤：

在去年清華的賽區上，有一個隊在做F題的時候使用了cout和printf的混合輸出，由於一個帶緩沖一個不帶，所以輸出一長就混亂了。只是因為當時judge team中負責F題的人眼睛尖，看出答案沒錯只是順序不對（答案有一頁多，是所有題目中最長的一個輸出），又看了看程序發現只是輸出問題就給了個Presentation error（格式錯）。如果審題的人不是這樣而是直接給一個 Wrong Answer，相信這個隊是很難查到自己錯在什麼地方的。

現在我們轉入第二個方面的討論，基礎學科知識的積累。

二、以數學為主的基礎知識十分重要

雖然被定性為程序設計競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的思路，而不是有了思路卻死活不能實現，這就是平時積累的基礎知識不夠。今年World Final的總冠軍是波蘭華沙大學，其成員出自於數學系而非計算機系，這就是一個鮮活的例子。競賽中對於基礎學科的涉及主要集中於數學，此外對於物理、電路等等也可能有一定應用，但是不多。因此，大一的同學也不必為自己還沒學數據結構而感到不知從何入手提高，把數學撿起來吧！下面我來談談在競賽中應用的數學的主要分支。

1、離散數學——作為計算機學科的基礎，離散數學是競賽中涉及最多的數學分支，其重中之重又在於圖論和組合數學，尤其是圖論。

圖論之所以運用最多是因為它的變化最多，而且可以輕易地結合基本數據結構和許多演算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關節點和關鍵路徑、歐拉迴路、最小生成樹、最短路徑、二部圖匹配和網路流等等。雖然這部分的比重很大，但是往往也是競賽中的難題所在，如果有初學者對於這部分的某些具體內容暫時感到力不從心，也不必著急，可以慢慢積累。

競賽中設計的組合計數問題大都需要用組合數學來解決，組合數學中的知識相比於圖論要簡單一些，很多知識對於小學上過奧校的同學來說已經十分熟悉，但是也有一些部分需要先對代數結構中的群論有初步了解才能進行學習。組合數學在競賽中很少以難題的形式出現，但是如果積累不夠，任何一道這方面的題目卻都有可能成為難題。

2、數論——以素數判斷和同餘為模型構造出來的題目往往需要較多的數論知識來解決，這部分在競賽中的比重並不大，但只要來上一道，也足以使知識不足的人冥思苦想上一陣時間。素數判斷和同餘最常見的是在以密碼學為背景的題目中出現，在運用密碼學常識確定大概的過程之後，核心演算法往往要涉及數論的內容。

3、計算幾何——計算幾何相比於其它部分來說是比較獨立的，就是說它和其它的知識點很少有過多的結合，較常用到的部分包括——線段相交的判斷、多邊形面積的計算、內點外點的判斷、凸包等等。計算幾何的題目難度不會很大，但也永遠不會成為最弱的題。

4、線性代數——對線性代數的應用都是圍繞矩陣展開的，一些表面上是模擬的題目往往可以藉助於矩陣來找到更好的演算法。

5、概率論——競賽是以黑箱來判卷的，這就是說你幾乎不能動使用概率演算法的念頭，但這也並不是說概率就沒有用。關於這一點，只有通過一定的練習才能體會。

6、初等數學與解析幾何——這主要就是中學的知識了，用的不多，但是至少比高等數學多，我覺得熟悉一下數學手冊上的相關內容，至少要知道在哪兒能查到，還是必要的。

7、高等數學——純粹運用高等數學來解決的題目我接觸的只有一道，但是一些題目的敘述背景往往需要和這部分有一定聯系，掌握得牢固一些總歸沒有壞處。

以上就是競賽所涉及的數學領域，可以說范圍是相當廣的。我認識的許多人去搞信息學的競賽就是為了逼著自己多學一點數學，因為數學是一切一切的基礎。

三、數據結構與演算法是真正的核心

雖然數學十分十分重要，但是如果讓三個只會數學的人參加比賽，我相信多數情況下會比三個只會數據結構與演算法的人得到更為悲慘的結局。

先說說數據結構。掌握隊列、堆棧和圖的基本表達與操作是必需的，至於樹，我個人覺得需要建樹的問題有但是並不多。（但是樹往往是很重要的分析工具）除此之外，排序和查找並不需要對所有方式都能很熟練的掌握，但你必須保證自己對於各種情況都有一個在時間復雜度上滿足最低要求的解決方案。說到時間復雜度，就又該說說哈希表了，競賽時對時間的限制遠遠多於對空間的限制，這要求大家盡快掌握「以空間換時間」的原則策略，能用哈希表來存儲的數據一定不要到時候再去查找，如果實在不能建哈希表，再看看能否建二叉查找樹等等——這都是爭取時間的策略，掌握這些技巧需要大家對數據結構尤其是演算法復雜度有比較全面的理性和感性認識。

接著說說演算法。演算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。這里要說的是，有些初學者在學習這些搜索基本演算法是不太注意剪枝，這是十分不可取的，因為所有搜索的題目給你的測試用例都不會有很大的規模，你往往察覺不出程序運行的時間問題，但是真正的測試數據一定能過濾出那些沒有剪枝的演算法。實際上參賽選手基本上都會使用常用的搜索演算法，題目的區分度往往就是建立在諸如剪枝之類的優化上了。

常用演算法中的另一類是以「相似或相同子問題」為核心的，包括遞推、遞歸、貪心法和動態規劃。這其中比較難於掌握的就是動態規劃，如何抽象出重復的子問題是很多題目的難點所在，筆者建議初學者仔細理解圖論中一些以動態規劃為基本思想所建立起來的基本演算法（比如Floyd-Warshall演算法），並且多閱讀一些定理的證明，這雖然不能有什麼直接的幫助，但是長期堅持就會對思維很有幫助。

四、團隊配合

通過以上的介紹大家也可以看出，信息學競賽對於知識面覆蓋的非常廣，想憑一己之力全部消化這些東西實在是相當困難的，這就要求我們盡可能地發揮團隊協作的精神。同組成員之間的熟練配合和默契的形成需要時間，具體的情況因成員的組成不同而不同，這里我就不再多說了。

五、練習、練習、再練習

知識的積累固然重要，但是信息學終究不是看出來的，而是練出來的，這是多少前人最深的一點體會，只有通過具體題目的分析和實踐，才能真正掌握數學的使用和演算法的應用，並在不斷的練習中增加編程經驗和技巧，提高對時間復雜度的感性認識，優化時間的分配，加強團隊的配合。總之，在這里光有紙上談兵是絕對不行的，必須要通過實戰來鍛煉自己。

大家一定要問，我們去哪裡找題做，又如何檢驗程序是否正確呢？這大可不必擔心，現在已經有了很多網上做題的站點，這些站點提供了大量的題庫並支持在線判卷，你只需要把程序源碼提交上去，馬上就可以知道自己的程序是否正確，運行所使用的時間以及消耗的內存等等狀況。下面我給大家推薦幾個站點，筆者不建議大家在所有這些站點上做題，選擇一個就可以了，因為每個站點的題都有一定的難易比例，系統地做一套題庫可以使你對各種難度、各種類型的題都有所認識。

1、Ural：

Ural是中國學生對俄羅斯的Ural州立大學的簡稱 ，那裡設立了一個Ural Online Problem Set，並且支持Online Judge。Ural的不少題目演算法性和趣聞性都很強，得到了國內廣大學生的厚愛。根據「信息學初學者之家」網站的統計，Ural的題目類型大概呈如下的分布：

題型
搜索
動態規劃
貪心
構造
圖論
計算幾何
純數學問題
數據結構
其它

所佔比例
約10%
約15%
約5%
約5%
約10%
約5%
約20%
約5%
約25%

這和實際比賽中的題型分布也是大體相當的。有興趣的朋友可以去看看。

2、UVA：

UVA代表西班牙Valladolid大學(University de Valladolid)。該大學有一個那裡設立了一個PROBLEM SET ARCHIVE with ONLINE JUDGE ，並且支持ONLINE JUDGE，形式和Ural大學的題庫類似。不過和Ural不同的是，UVA題目多的多，而且比較雜，而且有些題目的測試數據比較刁鑽。這使得剛到那裡做題的朋友往往感覺到無所適從，要麼難以找到合適的題目，要麼Wrong Answer了很多次以後仍然不知道錯在那裡。 如果說做Ural題目主要是為了訓練演算法，那麼UVA題目可以訓練全方位的基本功和一些必要的編程素質。UVA和許多世界知名大學聯合辦有同步網上比賽，因此那裡強人無數，不過你先要使自己具有聽懂他們在說什麼的素質：）

3、ZOJ：

ZOJ是浙江大學建立的ONLINE JUDGE，是中國大學建立的第一個同類站點，也是最好和人氣最高的一個，筆者和許多班裡的同學就是在這里練習。ZOJ雖然也定位為一個英文網站，但是這里的中國學生比較多，因此讓人覺得很親切。這里目前有500多道題目，難易分配適中，且涵蓋了各大洲的題目類型並配有索引，除此之外，ZOJ的JUDGE系統是幾個網站中表現得比較好的一個，很少出現Wrong Answer和Presentation error混淆的情況。這里每月也辦有一次網上比賽，只要是注冊的用戶都可以參加。

說起中國的ONLINE JUDGE，去年才開始參加ACM競賽的北京大學現在也建立了自己的提交系統；而我們學校也是去年開始參加比賽，現在也有可能推出自己的提交系統，如果能夠做成，到時候大家就可以去上面做題了。同類網站的飛速發展標志著有越來越多的同學有興趣進入信息學的領域探索，這是一件好事，同時也意味著更激烈的競爭。

看看這篇文章對你有什麼幫助！我也是ACM初學者！

㈢ 計算機相關專業想學習演算法，需要看哪些書

《演算法與數據結構》，《計算機組成原理,匯編語言》，《數字邏輯》，《編譯原理》，《計算機網路》，《面向對象的程序設計等》。

㈣ 淺談如何在面上中學開展《演算法與程序設計》教學

高中信息技術學科選修模塊《演算法與程序設計》內容枯燥、嚴謹，對於我們學生來說缺乏相關的知識背景，在高中階段才開始學習信息技術課難度大，也容易產生畏難情緒。那麼對於學生來說怎樣才能上好這門課呢？
一、首先教師應根據學生的實際情況，處理教材，分散難點
新課標指出：「學習本模塊旨在使學生進一步體驗演算法思想，了解演算法和程序設計在解決問題過程中的地位和作用；能從簡單問題出發，設計解決問題的演算法，並能初步使用一種程序設計語言編製程序實現演算法解決問題。」演算法是程序設計的靈魂，演算法教學是程序設計語言教學的基礎，程序設計語言教學是演算法教學的必要的延續。
教科版的《演算法與程序設計》，使用的編程語言是VisualBasic6.0。它和大多數程序設計語言書籍一樣，先花大量的篇幅介紹與VB語言開發環境及語法相關的基礎知識和基本概念，而後才開始程序三種基本結構的教學。教師根據學生的實際情況，對教材進行了處理、對內容進行調整，改變了教材中原有知識的邏輯結構順序。這樣學生可以邊用邊學，以用促學。
教師在每節課教學過程中都以簡單有趣的小問題為切入點，通過分析問題、設計演算法、編寫程序、調試運行，讓學生對演算法和程序設計有一個感性的認識，以降低學生的學習難度，並激發學生的學習興趣，觀摩、模仿、嘗試等階段逐漸到學生能獨立操作。開始選擇的例子比較簡單，如「在屏幕上輸出『studyVB』」、「已知三邊之長求三角形面積」、「計算前100個自然數之和」等。在此過程中適當忽略VB的可視化開發環境，其中數據的輸入只要求用inputbox()函數完成，數據的輸出直接用print語句在窗體完成，整個事件只要求由命令按鈕command1_click()來觸發，這樣的目的一方面是減少太多新知識對學生學習演算法思想的干擾，將難點分散，另一方面控制項少的程序也更容易上機調試通過，讓學生體驗成功的喜悅。
二、其次教師應聯系學生的數學知識，進行演算法與程序設計練習
演算法是解決問題的方法和步驟，計算機解決問題，必須嚴格地按步驟進行，這和我們平時解決問題是有區別的。因此在演算法設計中，應將解題的每一步都想清楚，對學生邏輯思維能力要求較高，許多同學剛開始不太適應。因此教師在教學過程中，精選教學案例，聯系學生的數學知識，從學生熟悉的或感興趣的數學問題出發，進行演算法與程序設計的練習。學生剛剛學習過海倫公式，在順序結構和選擇結構的教學中可採用「已知三邊長利用該公式來求三角形的面積」這個例子。因為學生有數學基礎，只要將解題步驟稍加修改就寫出如下演算法：
1．輸入三邊長；
2．求面積；
3．利用海倫公式s=p（p-a）（p-b）（p-c）,p=a+b+c2，求出面積s;
4．輸出面積s；
5．結束程序。
根據此演算法編寫好程序，在調試運行中發現如果三邊長為10，10，30時就不會輸出結果。那麼是為什麼呢？學生很快就想到這樣的三條邊是組不成三角形的，怎麼改？自然是輸入的a、b、c要先滿足兩邊之和大於第三邊才能組成三角形的，所以要在第二步之前添加一句，「如果不能同時滿足，就輸出『輸入數據錯誤』，轉5；否則轉2」。通過以上的例子，既體會到了演算法的嚴謹性，學生也學會了順序和選擇兩種結構的演算法描述。
教師還用趣味數學題來激發學生的興趣，如在學習過程中老師通過講解「水仙花數」、「百雞百錢」、「韓信點兵」、「棋盤上的麥粒」、「雞兔同籠」等問題來激發學生的學習興趣，以使大家的積極性得到提高。
三、一題多變，提高學生對知識的理解能力和編程能力
學生固有的認識框框和習慣的思維方式是學好演算法與程序設計的一大障礙。只有多實踐才能體會和認識到計算機解決問題的過程。然而由於課時限制，不可能有太多的時間來進行這方面的訓練。教師如能恰當地運用「一題多變」和「一題多解」等方法，精心選擇一道例題，讓它由淺入深循序變化，引導學生分析和比較，總結解決問題的一般規律，對弄清基本概念，提高解題能力以及培養思維的靈活性都是有益的。例如，對於「求s=1+2+3+4+5+6的一個演算法」就可以拓展以解決一類問題，如s=12+22+32+42+52+62，s=1+12+13+14+15+16，s=1-2+3-4+5-6，s=1×2×3×4×5×6等許多問題。這樣引導學生對比for-next以及do-loop循環的語法及適用情況。通過「一題多變」和「一題多解」的教學手段，使課堂效率得到了大大地提高。
四、教師應授之以漁，教會學生自己調試程序
《演算法與程序設計》模塊是作為計算機應用的技術基礎設置的，不能忽視技術，但我們強調的技術不再是以前那種「軟體說明書」式的操作。實際上對學生來說，犯的錯誤具有共性，主要是標點符號錯誤，比如「：」和「；」，關鍵詞與變數名之間沒有空格，語句書寫不完整，有if沒有endif，有for沒有next，變數名、對象名引用時出現拼寫錯誤等，其實學生只要掌握一點調試、運行程序的方法就能大大提高上機效率。通過訓練學生不但能自己調試程序，更能加深對程序的理解，尤其是到循環結構以後，這種作用就更明顯了，而且這種能力完全可以遷移到今後的學習和生活中去。
新課程目前還處在實驗階段，存在著很大的探索空間。對學生來說，激發他們的學習興趣、提高他們的積極性、不斷進行創新的同時提高教師自身的信息素養水平。教師不再只是教學者，更應該成為研究者和學習者，教師應加強教學反思，才能提高教學水平。