第1部分 各章重点和课后习题答案 3
第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.3 3种基本结构 12
2.2.4 3种调试工具 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部分 各类算法习题解析 95
第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.6 Jam的计数法 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
附录A ACM算法竞赛简介 221
A.1在线判题系统 221
A.1.1 OJ介绍 221
A.1.2 VJ介绍 221
A.2 ACM训练环境 221
A.2.1注册身份 221
A.2.2训练过程 222
A.2.3评测状态详解 224
A.3 ACM的算法知识点 225
A.3.1初级 225
A.3.2中级 227
A.3.3高级 228
附录B相关技术简介 231
B.1 STL 231
B.1.1简介 231
B.1.2容器 231
B.1.3算法 232
B.2头文件 232
附录C 3个软件算法竞赛简介 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