本书与《程序基本算法教程》(周元哲、刘伟、邓万宇编著)相配套,分为两部分。第1部分为主教材各章重点和课后习题答案,主要针对主教材各章(程序与算法、程序设计语言、数据结构、查找与排序、穷举法、递归法、分治法、动态规划法、贪心法、回溯法)的内容,介绍每章要求和知识重点,给出课后习题答案。第2部分为各类算法的习题解析,内容包括查找、穷举法、分治、动态规划、贪心法、回溯法和深度优先与广度优先,题目来自ACMICPC。附录给出ACM算法竞赛简介、相关技术简介和3个软件算法竞赛简介。

本书适合作为高等院校计算机软件及相关专业的教材或教学参考书,也可以供从事计算机应用开发的各类技术人员应用参考,或作为全国计算机等级考试、软件技术资格与水平考试和各类软件算法竞赛的培训资料。

本书与《程序基本算法教程》(周元哲、刘伟、邓万宇编著)相配套,分为两部分,第1部分共10章，为主教材各重点和课后习题答案。第2部分共7章，给出了查找、穷举法、分治、动态规划、贪心法、回溯法和深度优先与广度优先算法的习题解析,题目来自ACMICPC(ACM International Collegiate Programming Contest,ACM国际大学生程序设计竞赛),读者可注册网站https: //cn.vjudge.net/进行训练。附录给出ACM算法竞赛、相关技术和3个软件算法竞赛的简介。

西安邮电大学计算机学院刘伟、邓万宇编写相关章节的课后习题答案。西安邮电大学计算机学院计科14级的张浩然、袁子涵、干财进在第40届ACM国际大学生程序设计大赛东亚洲大陆子赛区总决赛ECFinal中获得铜奖,他们编写了第2部分。其余章节由周元哲编写,全书由周元哲负责大纲拟定与统稿工作。

学习程序基本算法的最好方法是实践,对于已经成型多年的经典算法,以习题为主,将抽象的理论知识应用于编码实践,才能扎实地掌握,深刻地理解这些算法。本书所有程序都在Visual C 6.0下调试运行通过,建议读者上机编写、运行和调试本书所给的例程。

西安邮电大学计算机学院的李晓戈、孟伟君、陈琳、舒新峰等审阅了某些章节。西安邮电大学ACM集训队的楚东方、刘敏、赵伟奇、郝希烜等同学调试了相关代码。清华大学出版社张民对本教材的写作大纲、写作风格等提出了很多宝贵的意见。衷心感谢上述各位的支持和帮助。在本书的写作过程中参阅了大量中外文的专著、教材、论文、报告及网络资料,在此向有关作者表示敬意和感谢。

本书可作为高等院校各专业学生学习程序设计和备战软件竞赛的辅导教材,也可作为程序员和社会读者的自学辅助用书。

由于作者水平有限,时间紧迫,本书难免有不足之处,我们诚恳期待读者的批评指正,以使本书日臻完善。我们的电子信箱是 zhouyuanzhe@163.com。

作者

2018年3月

第1部分各章重点和课后习题答案

第1章程序与算法/3

1.1本章要求/3

1.2本章知识重点/3

1.2.1程序/3

1.2.2算法/3

1.2.3算法的“2、3、5”/4

1.2.4算法复杂度/5

1.2.5算法学习步骤/6

1.3课后习题答案/6第2章程序设计语言/12

2.1本章要求/12

2.2本章知识重点/12

2.2.1结构化程序设计/12

2.2.2程序执行流程/12

2.2.33种基本结构/12

2.2.43种调试工具/15

2.3课后习题答案/15第3章数据结构/17

3.1本章要求/17

3.2本章知识重点/17

3.2.1概述/17

3.2.2数据结构研究对象/17

3.2.3线性表/18

3.2.4栈和队列/18

3.2.5二叉树/19

3.2.6图的遍历/21

3.2.7最短路径/23

3.3课后习题答案/26第4章查找与排序/30

4.1本章要求/30

4.2本章知识重点/30

4.2.1查找/30

4.2.2排序/32

4.2.3排序法总结/33

4.3课后习题答案/34第5章穷举法/40

5.1本章要求/40

5.2本章知识重点/40

5.2.1概述/40

5.2.2穷举法分类/40

5.3课后习题答案/40第6章递归法/46

6.1本章要求/46

6.2本章知识重点/46

6.2.1递归概念/46

6.2.2栈和堆/46

6.2.3基本递归/47

6.2.4尾递归/47

6.2.5相似术语解析/48

6.3课后习题答案/48第7章分治法/52

7.1本章要求/52

7.2本章知识重点/52

7.2.1分治法概念/52

7.2.2分治法适用的情况/52

7.2.3分治法的基本步骤/53

7.3课后习题答案/53第8章动态规划法/62

8.1本章要求/62

8.2本章知识重点/62

8.2.1动态规划特性/62

8.2.2动态规划分类/62

8.2.3动态规划求解步骤/63

8.3课后习题答案/64第9章贪心法/70

9.1本章要求/70

9.2本章知识重点/70

9.2.1贪心算法概念/70

9.2.2贪心算法的两个性质/70

9.2.3贪心算法解题步骤/71

9.2.4贪心算法和动态规划的关系/71

9.3课后习题答案/72第10章回溯法/79

10.1本章要求/79

10.2本章知识重点/79

10.2.1回溯概念/79

10.2.2回溯求解步骤/79

10.3课后习题答案/85

第2部分各类算法习题解析第11章查找/95

11.1寻找字符串/95

11.2最小的因子对差/96

11.3能否获胜/97

11.4能解决多少任务/99

11.5最高等级/100

11.6执行任务/102

11.7变化字符串的数目/104

11.8两个人的比赛/106

11.9选择购物券/109

11.10分蛋糕/111

11.11求先序排列/113

11.12字符串匹配/114第12章穷举/116

12.1证明错误假设/116

12.2平行四边形第4个顶点/117

12.3能否组成n/118

12.4更改时间/119

12.5捉住小偷/122

12.6Jam的计数法/124

12.7线段/126

12.8求合数和/127

12.9数字挑战/128

12.10子字符串/130第13章分治/133

13.1排列/133

13.2组合/135

13.3线性时间选择/137

13.4一维最接近点对问题/140

13.5循环赛日程表/145第14章动态规划/148

14.1线段覆盖/148

14.2过河卒/149

14.3装箱问题/151

14.4乘积最大/153

14.5数的划分/154

14.6统计单词个数/156

14.7给树上色/159

14.8写作业/161

14.9炸弹/164

14.10拦截导弹/166

14.11入学考试/168第15章贪心法/170

15.1均分纸牌/170

15.2胸有成竹/171

15.3今年暑假不AC/173

15.4手机控/175

15.5握手/176

15.6万圣节/178

15.7逆序对数/179

15.8操作字符串/181

15.9吃货/183

15.10二进制/184

15.11奶牛飞车/185

15.12多处最优服务/187

15.13删除问题/189

15.14小船过河问题/190第16章回溯法/193

16.1八数码/193

16.2素数环/194

16.3素数环的排列/196

16.4符号三角形问题/198

16.5迷宫问题/200第17章深度优先与广度优先/204

17.1油田计数/204

17.2伪二进制/206

17.3越过山丘/207

17.4翻转道路/210

17.5单词接龙/212

17.6最少步数/214

17.7相邻数之和为素数/216附录AACM算法竞赛简介/221

A.1在线判题系统/221

A.1.1OJ介绍/221

A.1.2VJ介绍/221

A.2ACM训练环境/221

A.2.1注册身份/221

A.2.2训练过程/222

A.2.3评测状态详解/224

A.3ACM的算法知识点/225

A.3.1初级/225

A.3.2中级/227

A.3.3高级/228附录B相关技术简介/231

B.1STL/231

B.1.1简介/231

B.1.2容器/231

B.1.3算法/232

B.2头文件/232附录C3个软件算法竞赛简介/233

C.1竞考网/233

C.2团体程序设计天梯赛/234

C.2.1历史背景/234

C.2.2参赛队组成/234

C.2.3竞赛规则/235

C.2.4命题与竞赛评分/235

C.2.5竞赛环境和竞赛语言/237

C.2.6获奖比例/237

C.2.7报名方法/238

C.3中国软件杯/239参考文献/240

本书程序基本算法解析全面、经典实用、综合性强，题目来自ACM ICPC，着重提高编程应用开发能力。

本书与《程序基本算法教程》（周元哲、刘伟、邓万宇编著）相配套，分为两部分。第1部分为主教材各章重点和课后习题答案，主要针对主教材各章（程序与算法、程序设计语言、数据结构、查找与排序、穷举法、递归法、分治法、动态规划法、贪心法、回溯法）的内容，介绍每章要求和知识重点，给出课后习题答案。第2部分为各类算法的习题解析，内容包括查找、穷举法、分治、动态规划、贪心法、回溯法和深度优先与广度优先，题目来自ACM ICPC。附录给出ACM算法竞赛简介、相关技术简介和3个软件算法竞赛简介。

本书适合作为高等院校计算机软件专业的教材或教学参考书，也可以供从事计算机应用开发的各类技术人员应用参考，或作为全国计算机等级考试、软件技术资格与水平考试和各类软件算法竞赛的培训资料。

本书程序基本算法解析全面、经典实用、综合性强，题目来自ACM ICPC，着重提高编程应用开发能力。

本书与《程序基本算法教程》（周元哲、刘伟、邓万宇编著）相配套，分为两部分。第1部分为主教材各章重点和课后习题答案，主要针对主教材各章（程序与算法、程序设计语言、数据结构、查找与排序、穷举法、递归法、分治法、动态规划法、贪心法、回溯法）的内容，介绍每章要求和知识重点，给出课后习题答案。第2部分为各类算法的习题解析，内容包括查找、穷举法、分治、动态规划、贪心法、回溯法和深度优先与广度优先，题目来自ACM ICPC。附录给出ACM算法竞赛简介、相关技术简介和3个软件算法竞赛简介。

本书适合作为高等院校计算机软件专业的教材或教学参考书，也可以供从事计算机应用开发的各类技术人员应用参考，或作为全国计算机等级考试、软件技术资格与水平考试和各类软件算法竞赛的培训资料。