突出應用，針對實際

項目驅動，案例引導

行業專家，教育前沿

ACM國際大學生程序設計競賽（簡稱ACM）由國際計算機界歷史悠久、頗具權威性的組織ACM學會主辦，是世界上公認的規模最大、水平最高的國際大學生程序設計競賽，目的在于讓大學生運用計算機充分展示自己分析問題、解決問題的能力。該項賽事云集了世界上的計算機精英和希望之星，受到國際社會各方的高度重視，已經成為世界上最具影響力的國際級計算機類大賽。ACM賽事不僅能培養參賽者的程序開發能力和創造能力，更能培養團隊合作精神以及解決問題的創新思維，還能測試參賽選手的抗壓能力。

另一方面，創新創業教育是以培育高校大學生的創新精神、創業意識、創新創業能力為主的教育，是一種側重創新思維培養和創業能力鍛煉的實用教育。近年來，由于高校教學與社會需求之間存在一定的脫節，導致大量計算機等專業畢業生不能直接進入社會創造實際價值，而需要到培訓機構進行回爐再造。因此，在當前“大眾創業、萬眾創新”的深化高等教育改革新形勢下，如何在互聯網+信息大數據時代有效推進計算機相關學科大學生的創新創業能力培養顯得尤為關鍵。

在這樣的背景下，應用型普通本科院校以ACM競賽為導引，融入創新創業教育，探索與實踐新的計算機科學與技術專業人才培養模式，不僅對于學生個人，而且對于學科專業、高等學校，甚至對于整個社會都具有重要的意義。從這個意義上說，ACM程序設計是培養大學生綜合素質和創新精神的一種有效手段和重要載體，對于營造創新創業教育的良好氛圍，推進校風學風建設，培養學生的創新精神、協作意愿和實踐能力，激發學生的學習興趣和潛能都具有重要作用。最終可以促進高校創新創業人才培養教育教學改革有效落實，激發在校大學生跨學科多元化創新創業的熱情，有力地推動了高等教育教學創新人才培養改革實踐。

這本基礎性教材的編寫目的在于幫助各個地方應用型本科高校的大學生們了解國際大學生程序設計競賽、了解其程序設計的方法和思路，提高他們參與各級ACM競賽的興趣，更重要的是通過以ACM程序設計為載體的訓練有效地提高大學生的計算機學科綜合素質和創新意識。

本教材共分10章：

第1章 概述，主要介紹了與ACM競賽有關的各類賽事，包括國際ACM競賽、廣東GDCPC競賽、全國藍橋杯大賽、中國計算機學會軟件能力認證、國際青少年信息學奧林匹克競賽等。

第2章 入門基礎，主要介紹了數據的輸入輸出格式、基本編程環境與方法、在線系統的使用、常見錯誤及其對策、字符串處理等，大多數問題都比較容易，尤其適合ACM程序設計的初學者作為入門訓練。

第3章 蠻力法，主要介紹了蠻力法這種最典型、最直接的問題求解方法，包括基本思想、實例分析、程序優化策略等。

第4章 數學問題，主要闡明了與ACM程序設計最密切的一個專題，重點展開了數論、計算幾何、組合、概率等知識的學習。

第5章 分治、遞歸與遞推，主要闡釋了最常用的分治遞歸以及遞推策略。通過實例剖析了遞歸與遞推的關系，以及相互之間的轉換。

第6章 高精度計算與模擬法，主要講解了ACM程序設計中也是實際生活中經常使用的大數高精度計算問題，并以此引出一種模擬法的求解問題思路。

第7章 排序與查找，作為計算機科學中的兩個經典問題，在很多ACM程序設計中都有具體應用，舉例闡明了這些問題的求解策略及其應用。

第8章 貪心法，作為問題求解的常用算法之一，介紹了其基本概念、核心思想、一般步驟，通過四個經典問題并配以若干實例分析了貪心策略。

第9章 動態規劃法，作為ACM程序設計中必定涉及的一類方法，介紹了其基本概念、核心思想、一般步驟，通過若干實例分析了動態規劃法的求解策略。

第10章 并查集，簡單介紹了一個特別高效的數據結構及其使用。

本書由吳濤任主編，劉宇欣、張立敏、吳東、梁㑇任副主編。在編寫過程中，編者參考并引用了大量ACM競賽和程序設計方面的資料，特別是網絡資料，限于篇幅和來源，無法一一羅列，在此對這些資料的貢獻者致以衷心的感謝。

本書的出版得到了廣東高校優秀青年教師培養計劃項目（編號：YQ2014117）、廣東省計算機科學與技術專業綜合改革試點項目（粵教高函〔2013〕113號）、廣東省計算機實驗教學示范中心項目（粵教高函〔2015〕133號），以及嶺南師范學院2017年校級高等教育教學改革項目（ACM競賽引導的個性化工科創新思維教學改革）等經費的資助。

最后，衷心祝愿讀者能夠從本書中獲益，品味ACM程序設計帶來的算法思維藝術之美，并實現自己的創新創業夢想。

由于作者水平有限，書中難免存在不妥之處，敬請廣大讀者批評指正（聯系郵箱：wu_tao0706@sina.com）；讀者也可以就相關問題直接通過學者網主頁與作者進行交流（網址：http://www.scholat.com/taowu0706）。

第1章 概述 1
1.1 國際ACM競賽 1
1.2 廣東GDCPC競賽 2
1.3 全國藍橋杯大賽 3
1.4 中國計算機學會軟件能力認證 4
1.5 國際青少年信息學奧林匹克競賽 5
1.6 本章小結 7
1.7 本章思考 7
第2章 入門基礎 8
2.1 輸入輸出 8
2.2 開發環境與使用 11
2.2.1 Visual C++ 13
2.2.2 Dev-C++ 14
2.2.3 Visual Studio 16
2.2.4 Code Blocks 17
2.3 入門題 19
2.4 字符串處理 25
2.5 算法分析基礎 35
2.6 本章小結 37
2.7 本章思考 37
第3章 蠻力法 38
3.1 基本思想 38
3.2 實例分析 39
3.3 程序優化 49
3.4 本章小結 56
3.5 本章思考 56
第4章 數學問題 57
4.1 概述 57
4.2 數論問題 65
4.2.1 同余 65
4.2.2 素數 77
4.3 計算幾何 88
4.4 組合問題 97
4.5 概率問題 102
4.6 本章小結 112
4.7 本章思考 112
第5章 分治、遞歸與遞推 113
5.1 分治 113
5.2 遞歸 121
5.3 遞推 128
5.4 本章小結 136
5.5 本章思考 136
第6章 高精度計算與模擬法 137
6.1 大數高精概述 137
6.2 大整數加法 140
6.3 大整數減法 147
6.4 大整數乘法 150
6.5 模擬法 152
6.6 本章小結 161
6.7 本章思考 161
第7章 排序與查找 162
7.1 排序 162
7.2 查找 170
7.2.1 靜態查找 170
7.2.2 動態查找 174
7.3 排序與查找的應用 177
7.4 本章小結 198
7.5 本章思考 198
第8章 貪心法 199
8.1 基本概念 199
8.2 核心思想 199
8.3 一般步驟 200
8.4 經典問題的貪心策略 201
8.4.1 活動安排問題 201
8.4.2 哈夫曼編碼問題 202
8.4.3 最小生成樹問題 204
8.4.4 背包問題 207
8.5 實例分析 208
8.6 本章小結 221
8.7 本章思考 221
第9章 動態規劃法 223
9.1 基本概念 223
9.2 一般步驟 224
9.3 核心思想 225
9.4 實例分析 234
9.5 本章小結 245
9.6 本章思考 246
第10章 并查集 247
10.1 基本概念 247
10.2 核心操作 247
10.3 實例分析 248
10.4 本章小結 258
10.5 本章思考 258
附錄 解題報告模板 259
參考文獻 260

1. 輸水管線工程風險管理 [張勇 黨亥生 著]
2. 民用航空飛機標準線路施工 [主編　王志敏　陳明]
3. 不息的水脈—大運河講談錄 [趙珩　著]
4. 實用運籌學 [主編　邢育紅　于晉臣]
5. 三峽梯級電站水資源決策支持系統研究與開發 [姚華明 潘紅忠 湯正]
6. 海南黎族民俗文化鑒賞 [龐國華　著]
7. 石墨烯在太赫茲及中紅外頻段電磁器件設計中的應用 [李艷秀 莊華偉 著]
8. 電子技術（第二版） [主編 覃愛娜 李飛]
9. 辦公自動化高級應用 [陳萍 朱曉玉]
10. 信息處理技術員考試32小時通關 [薛大龍]
11. 電子產品設計案例教程（微課版）—基于嘉立創EDA（專業版） [王靜 莫志宏 陳學昌 丁紅]
12. C程序設計實踐教程 [劉衛國]
13. C程序設計（慕課版） [劉衛國]
14. Web技術開發教程（基于.NET開源MVC框架） [王合闖 韓紅玲 王青正 陳海蕊]
15. 商務英語翻譯教程（筆譯）（第四版） [主編 王軍平]
16. 智慧零售技術與應用 [洪旭 著]
17. 建設工程法規實務 [主編 余瀅]
18. 商務秘書理論與實務（第三版） [主編 張同欽]
19. 程序設計基礎實踐教程（C/C++語言版） [張桂芬 葛麗娜]
20. C++案例項目精講 [主編 楊國興]
21. 勞動爭議處理實務 [主編 王秀卿 羅靜]
22. 工程數學 [主編 郭立娟 王海]
23. 語音識別理論與實踐 [主編　莫宏偉]
24. 信息系統項目管理師章節習題與考點特訓（第二版） [主編 薛大龍]
25. 武術基礎教程 [主編 李代勇 謝志民]
26. 計算機網絡實訓教程 [主編 張浩軍 趙玉娟]
27. 畫法幾何與機械制圖習題集（多學時） [主編 趙軍]
28. HCIA-Datacom認證題庫分類精講 [主 編 韓立剛]
29. SwiftUI完全開發 [李智威 著]
30. 網絡規劃設計師備考一本通 [夏杰 編著]