ACM程序設(shè)計(jì)基礎(chǔ)

突出應(yīng)用，針對實(shí)際

項(xiàng)目驅(qū)動，案例引導(dǎo)

行業(yè)專家，教育前沿

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

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

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

這本基礎(chǔ)性教材的編寫目的在于幫助各個(gè)地方應(yīng)用型本科高校的大學(xué)生們了解國際大學(xué)生程序設(shè)計(jì)競賽、了解其程序設(shè)計(jì)的方法和思路，提高他們參與各級ACM競賽的興趣，更重要的是通過以ACM程序設(shè)計(jì)為載體的訓(xùn)練有效地提高大學(xué)生的計(jì)算機(jī)學(xué)科綜合素質(zhì)和創(chuàng)新意識。

本教材共分10章：

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

第2章 入門基礎(chǔ)，主要介紹了數(shù)據(jù)的輸入輸出格式、基本編程環(huán)境與方法、在線系統(tǒng)的使用、常見錯(cuò)誤及其對策、字符串處理等，大多數(shù)問題都比較容易，尤其適合ACM程序設(shè)計(jì)的初學(xué)者作為入門訓(xùn)練。

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

第4章 數(shù)學(xué)問題，主要闡明了與ACM程序設(shè)計(jì)最密切的一個(gè)專題，重點(diǎn)展開了數(shù)論、計(jì)算幾何、組合、概率等知識的學(xué)習(xí)。

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

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

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

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

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

第10章 并查集，簡單介紹了一個(gè)特別高效的數(shù)據(jù)結(jié)構(gòu)及其使用。

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

本書的出版得到了廣東高校優(yōu)秀青年教師培養(yǎng)計(jì)劃項(xiàng)目（編號：YQ2014117）、廣東省計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)綜合改革試點(diǎn)項(xiàng)目（粵教高函〔2013〕113號）、廣東省計(jì)算機(jī)實(shí)驗(yàn)教學(xué)示范中心項(xiàng)目（粵教高函〔2015〕133號），以及嶺南師范學(xué)院2017年校級高等教育教學(xué)改革項(xiàng)目（ACM競賽引導(dǎo)的個(gè)性化工科創(chuàng)新思維教學(xué)改革）等經(jīng)費(fèi)的資助。

最后，衷心祝愿讀者能夠從本書中獲益，品味ACM程序設(shè)計(jì)帶來的算法思維藝術(shù)之美，并實(shí)現(xiàn)自己的創(chuàng)新創(chuàng)業(yè)夢想。

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

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

1. 零基礎(chǔ)玩轉(zhuǎn)國產(chǎn)大模型DeepSeek [徐永冰 張帥 編著]
2. 網(wǎng)絡(luò)工程師5天修煉（適配第6版考綱） [主編　朱小平 施游]
3. 信息系統(tǒng)項(xiàng)目管理師考試32小時(shí)通關(guān)（適用第4版考綱） [薛大龍]
4. 信息系統(tǒng)管理工程師考試32小時(shí)通關(guān)（適配第2版考綱） [薛大龍　劉偉]
5. 土木工程材料檢測實(shí)訓(xùn) [洪曉江 達(dá)則曉麗 錢波]
6. 科技信息檢索與論文寫作實(shí)用教程 [李振華]
7. 傳統(tǒng)山水畫論解讀與實(shí)踐 [陳鈉 著]
8. Python數(shù)據(jù)庫編程 [主編 殷樹友 邢 翀]
9. 計(jì)算機(jī)基礎(chǔ)實(shí)訓(xùn)指導(dǎo) [主編 袁春萍 朱妮]
10. 嵌入式人工智能技術(shù)應(yīng)用（數(shù)字教材） [主編 胡娜 楊國勇 晏廷榮]
11. Vienna整流器技術(shù) [桂存兵 著]
12. 變頻器與伺服應(yīng)用 [陳剛 葉云飛]
13. 物聯(lián)網(wǎng)工程設(shè)計(jì)與實(shí)踐 [湯琳 李敏]
14. 爐邊夜話——深入淺出話AI [汪建　著]
15. 電商運(yùn)營與管理 [鐘肖英 陳瀟]
16. Java面向?qū)ο蟪绦蛟O(shè)計(jì) [主編 姜春磊 陳虹潔]
17. 信息技術(shù)基礎(chǔ)（Windows 10+WPS Office）（微課版） [主編　石利平　田輝平　謝盛嘉]
18. 人工智能應(yīng)用 [主編　陳　萍　劉培培　陳孟軍]
19. 大學(xué)生職業(yè)發(fā)展與就業(yè)指導(dǎo) [主編　劉志堅(jiān)]
20. 高級辦公應(yīng)用項(xiàng)目教程 [主編 屈晶 趙成麗]
21. 微信小程序開發(fā)項(xiàng)目實(shí)戰(zhàn)（微課版） [主編 黃龍泉 郭峰 朱倩]
22. 企業(yè)檔案工作實(shí)戰(zhàn)寶典百問百答 [華俊 盧秀英 邵甜甜 著]
23. 計(jì)算機(jī)網(wǎng)絡(luò)原理及應(yīng)用 [主編 唐繼勇 葉坤 孫夢娜]
24. 大學(xué)生創(chuàng)業(yè)基礎(chǔ) [主編 王麗莉 王 楊]
25. 船舶輔機(jī) [主編 王連海 于洋 姜淑翠]
26. 大學(xué)生就業(yè)指導(dǎo) [主編 王麗莉 董宴廷]
27. 系統(tǒng)架構(gòu)設(shè)計(jì)師章節(jié)習(xí)題與考點(diǎn)特訓(xùn) [主編 薛大龍 鄒月平]
28. 高校學(xué)生工作探索與實(shí)踐 [郭亮 著]
29. 大學(xué)生情商管理 [方雄 著]
30. 2023年長沙市會展業(yè)發(fā)展報(bào)告 [主編 周棟良]