ACM程序设计基础

中国水利水电出版社

【作者】吴涛

【I S B N 】978-7-5170-6214-1

【责任编辑】封裕

【适用读者群】本专通用

【出版时间】2018-05-07

【开本】16开

【装帧信息】平装（光膜）

【版次】第1版第1次印刷

【页数】268

【千字数】415

【印张】16.75

【定价】￥38

【丛书】普通高等教育“十三五”规划教材（软件工程专业）

【备注信息】

图书详情

简介

本书特色

前言

章节列表

精彩阅读

下载资源

相关图书

本书以ACM竞赛为导引，融入创新创业教育，探索与实践新的计算机科学与技术专业人才培养模式，不仅对于学生个人，而且对于学科专业、高等学校，甚至对于整个社会都具有重要的意义。ACM程序设计是培养计算机科学技术、软件工程、物联网工程等专业大学生综合素质和创新精神的一种有效手段和重要载体。这本基础性教材的编写目的在于帮助大学生了解国际大学生程序设计竞赛，了解其程序设计的方法和思路，提高学生参与各级ACM竞赛的兴趣，更重要的是以ACM程序设计为载体对学生进行思维训练，有效地提高大学生的计算机学科综合素质和创新意识。

本书共分10章，包括ACM程序设计概述，入门基础，蛮力法，数学问题，分治、递归与递推，高精度计算与模拟法，排序与查找，贪心法，动态规划法，并查集等专题。其中提供了大量ACM程序设计教学案例，适合作为应用型普通高等院校计算机科学技术、软件工程、物联网工程等相关专业的本专科学生拓展ACM创新思维或参加ACM竞赛的初级辅助性教程，也适合作为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

关闭

打印