ACM程序设计基础

突出应用，针对实际

项目驱动，案例引导

行业专家，教育前沿

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. 网络规划设计师备考一本通 [夏杰 编著]