算法设计与问题求解(第2版·微课版)

第1章算法基础1
1.1算法概念1
1.2算法描述1
1.3算法主要类别及典型问题2
1.3.1递归法2
1.3.2递推法2
1.3.3穷举法3
1.3.4贪心算法3
1.3.5分治法4
1.3.6动态规划法4
1.3.7分支限界法5
1.3.8回溯法6
1.4算法复杂度6
1.4.1算法输入规模度量6
1.4.2算法运行时间的度量7
1.4.3渐进符号7
1.4.4算法复杂度分析8
1.5标准模板库13
1.5.1动态数组vector的使用13
1.5.2集合set的使用15
1.5.3映射map的使用16
1.5.4栈stack的使用18
1.5.5队列与优先队列的使用19
1.5.6排序sort的使用22
习题24
第2章递归算法设计25
2.1概念25
2.2递归算法设计思想25〖3〗算法设计与问题求解（第2版·微课版）目录〖3〗2.3递归算法示例与过程分析26
2.3.1全排列问题26
2.3.2逆波兰表达式28
2.4递归转换30
2.4.1递归转尾递归30
2.4.2递归转非递归31
2.5能力拓展35
2.5.1K数列35
2.5.2自关联树状数据36
2.5.3XML文件解析39
习题43
第3章蛮力法46
3.1概述46
3.2蛮力法的主要设计思想46
3.2.1使用蛮力法的几种情况46
3.2.2蛮力法的求解步骤46
3.3蛮力法示例与分析47
3.3.1选择排序47
3.3.2旅行商问题48
3.3.3字符串匹配蛮力解决50
3.3.401背包问题52
3.4能力拓展53
3.4.1连续数和53
3.4.2矩形个数54
习题56
第4章分治法59
4.1概述59
4.2分治法设计思路59
4.3分治法应用与过程分析62
4.3.1*大子段和62
4.3.2归并排序63
4.3.3棋盘覆盖问题65
4.3.4*近点对问题68
4.3.5快速排序70
4.4能力拓展73
4.4.1二进制的完全表示73
4.4.2求两个等长有序序列的中位数74
4.4.3找第k大的元素76
习题78
第5章回溯法80
5.1概述80
5.2回溯法设计思路80
5.3回溯法示例与过程分析81
5.3.1n皇后问题81
5.3.201背包问题83
5.3.3图的m着色问题85
5.3.4批处理作业调度问题88
5.4能力拓展91
5.4.1全排列问题91
5.4.2存在障碍物的迷宫问题93
5.4.3*少考场数量95
习题97
第6章贪心法103
6.1概述103
6.2贪心算法步骤及适用的问题103
6.2.1贪心算法步骤103
6.2.2适用贪心算法求解问题的特点103
6.3贪心算法示例与过程分析104
6.3.1部分背包问题104
6.3.2*优装载问题106
6.3.3区间调度问题107
6.3.4旅行商问题108
6.4能力拓展110
6.4.1*小正整数110
6.4.2数字游戏111
6.4.3关闭闹钟113
6.4.4过河114
习题117
第7章分支限界法121
7.1概述121
7.2分支限界法设计思路121
7.3分支限界法示例与过程分析123
7.3.101背包问题123
7.3.2多段图*短路径问题125
7.3.3旅行商问题127
7.3.4作业调度问题132
7.4能力拓展137
7.4.1大富翁游戏137
7.4.2*优装载问题138
习题141
第8章动态规划144
8.1概述144
8.2动态规划算法设计规则144
8.3动态规划算法问题求解145
8.3.101背包问题145
8.3.2*长公共子序列149
8.3.3*长上升子序列153
8.3.4字符串相似度/编辑距离158
8.3.5*大子段和160
8.4能力拓展163
8.4.1带通配符的字符串匹配163
8.4.2拼图167
习题170
第9章图算法设计174
9.1概述174
9.1.1图的定义174
9.1.2图的相关概念174
9.2图算法示例与分析175
9.2.1*短路问题175
9.2.2网络*大流问题179
9.2.3二分图染色问题182
9.3能力拓展184
9.3.1杂交育种184
9.3.2小偷逃跑188
9.3.3朋友满意数量188
习题192
第10章计算几何199
10.1概述199
10.2相关几何知识200
10.2.1向量200
10.2.2点积和叉积202
10.2.3基本应用203
10.2.4点是否在面内204
10.2.5方向204
10.2.6面积和角度205
10.2.7凸性205
10.3计算几何示例与分析206
10.3.1点到直线的距离、判断线段是否相交206
10.3.2凸包问题(极角排序)210
10.3.3利用叉积计算多边形面积212
10.4能力拓展214
10.4.1不同直线计数214
10.4.2面积*大的三角形215
10.4.3面积*大的多边形218
习题221
第11章计算复杂度理论227
11.1计算模型227
11.2P类和NP类问题231
11.3NPC问题233
习题234
第12章概率算法和近似算法236
12.1概率算法236
12.1.1概率算法的基本概念236
12.1.2概率算法的分类237
12.1.3数值概率算法237
12.1.4舍伍德算法238
12.1.5拉斯维加斯算法240
12.1.6蒙特卡罗算法243
12.2近似算法246
12.2.1介绍246
12.2.2顶点覆盖问题247
12.2.3旅行商问题248
习题249