算法设计基础与应用

《算法设计基础与应用》具有基础性（循序渐进地介绍算法设计的主要理论）、趣味性（将待解决的复杂问题编成通俗易懂的故事）、丰富性（涵盖算法设计相关的主要理论和知识点）、实用性（强调理论与实践相结合）、针对性（适合研究算法和参加各类程序设计竞赛人员使用）等特点，同时，本教材配套了相应的电子教案和例题讲解视频，访问书内网址或扫描书内二维码即可免费获得。

本书共分为14章，其中前3章主要介绍了与算法设计相关的一些必须了解和掌握的常识和概念，在后续的章节里，介绍了蛮力、递推、模拟、分治、贪心、动态规划、搜索等常用算法策略，以及最短路径、二分图、网络流、并査集、数论、博弈等经典算法。在例题的设计上采用的是ACM竞赛试题的模式，实现的语言是C/C++。本书既可作为高等院校计算机及其相关专业高年级本科生和研究生算法设计课程的教材，也可作为广大计算机工作者、编程爱好者的参考用书。

 

第1章程序设计相关基本概念1
1.1程序的组成1
1.2函数、函数嵌套和函数递归3
1.3数据类型所占字节数4
1.4内存空间的开辟5
1.5算法的时间复杂度和空间复杂度6
第2章C++模板库9
2.1标准模板库STL简介9
2.2模板库的典型应用11
2.3本章小结27
第3章算法设计常用技巧及优化策略28
3.1程序设计主要原则28
3.2空间换时间30
3.3数学模型的建立32
3.4数组的应用33
3.5信息数字化34
3.6标志量的使用36
思考题38
第4章蛮力法42
4.1蛮力法的定义42
4.2蛮力法的算法框架43
4.3经典例题解析43
4.4本章小结49
思考题49
第5章模拟策略51
5.1模拟策略的概念51
5.2经典例题解析51
5.3本章小结59
思考题60
第6章递推策略62
6.1递推策略的定义63
6.2递推策略解决问题的步骤63
6.3经典例题解析64
6.4本章小结68
思考题68
第7章分治策略70
7.1分治策略的设计思想70
7.2分治策略的基本步骤70
7.3分治策略算法框架70
7.4经典例题解析71
7.5本章小结84
思考题84
第8章贪心策略87
8.1贪心算法的定义87
8.2贪心算法的步骤87
8.3贪心算法的框架88
8.4经典例题解析88
8.5本章小结100
思考题100
第9章动态规划103
9.1动态规划所要解决问题的特征105
9.2动态规划处理问题的思想105
9.3动态规划处理问题的步骤106
9.4经典例题解析106
9.5本章小结126
思考题126
第10章搜索130
10.1图的基本概念130
10.2回溯法134
10.3分支限界法161
10.4本章小结181
思考题181
第11章图论的应用185
11.1*短路径问题185
11.2二分图209
11.3网络流219
思考题231
第12章并查集234
12.1并查集的定义234
12.2并查集算法框架235
12.3并查集算法优化策略238
12.4并查集应用240
12.5本章小结248
思考题248
第13章数论251
13.1欧几里得定理及应用251
13.2素数的测试——Eratosthenes筛法255
13.3同余问题258
13.4容斥定理262
13.5母函数264思考题268
第14章博弈论271
14.1博弈的定义271
14.2几个经典博弈方法272
14.3博弈论的应用274
14.4本章小结280思考题280
附录：在线判题系统（OJ）简介282
参考文献287