算法设计与分析实用教程PDF电子书下载

第1章 算法及其复杂性分析 1

1.1算法及其描述 1

1.1.1算法定义与特性 1

1.1.2算法描述 3

1.2算法复杂性分析 7

1.2.1算法的时间复杂度 7

1.2.2算法的空间复杂度 12

1.2.3 NP完全问题 12

1.3算法设计与分析实例 13

1.3.1求解最大公约数 13

1.3.2计算n！ 14

1.3.3全码倍数搜索 16

1.4算法与程序设计 17

1.4.1算法与程序 17

1.4.2结构化程序设计 21

习题1 23

第2章 枚举 26

2.1枚举概要 26

2.2统计求和 27

2.2.1同码小数 27

2.2.2三角网格 30

2.3整数搜索 32

2.3.1整数对 32

2.3.2基于s的双和数组 33

2.3.3最小连续m个合数 34

2.4解方程与不等式 37

2.4.1佩尔方程 37

2.4.2分数不等式 38

2.5数式与运算 40

2.5.1奇数序列运算式 40

2.5.2完美综合运算式 41

2.6数列与数阵 44

2.6.1 H形数序列 44

2.6.2三阶素数幻方 46

2.7表格与图形 48

2.7.1 p进制乘法表 48

2.7.2基于s的和积三角形 49

2.8枚举设计的改进与优化 52

2.8.1选择枚举路线 52

2.8.2精简枚举结构 54

2.8.3优化枚举参数 55

习题2 56

第3章 递推 59

3.1递推概述 59

3.1.1递推的概念 59

3.1.2递推常用模式 60

3.2递推数列 61

3.2.1双关系递推数列 62

3.2.2振动数列 63

3.2.3分数数列 65

3.3超级素数搜索 66

3.4数阵与网格 69

3.4.1杨辉三角 69

3.4.2方格网交通线路 71

3.5六六顺数组 73

3.6猴子爬山 76

3.6.1简单递推设计 76

3.6.2分级递推设计 77

3.7整数划分 79

3.7.1整数划分式的个数 79

3.7.2整数划分式的实现 80

3.7.3实现整数划分式的优化 82

3.8递推与迭代 84

习题3 86

第4章 递归 88

4.1分治策略与递归 88

4.2汉诺塔游戏 92

4.2.1移动次数求解 93

4.2.2移动过程实现 94

4.3排队购票问题 96

4.3.1常规排队 96

4.3.2带条件限制的排队 98

4.4多转向旋转方阵 100

4.5快速排序与选择 102

4.5.1分区交换排序 103

4.5.2分区交换选择 105

4.6实现排列组合 107

4.6.1基本排列实现 107

4.6.2复杂排列实现 109

4.6.3组合实现 111

4.7整数的拆分式 113

4.8递归与递推 115

习题4 117

第5章 回溯法 119

5.1回溯法概述 119

5.1.1回溯的概念 119

5.1.2回溯的数学概括与效益分析 120

5.1.3回溯法的分类 121

5.2桥本分数式 124

5.3直尺与串珠 127

5.3.1古尺神奇 127

5.3.2数码串珠 129

5.4逐位整除数 132

5.4.1回溯探索 132

5.4.2递推求解 133

5.5二组均分 135

5.6伯努利装错信封问题 136

5.6.1回溯设计 137

5.6.2递归探索 138

5.7情侣拍照 140

5.7.1逐位安排回溯设计 140

5.7.2成对安排回溯设计 142

5.8回溯应用小结 144

习题5 145

第6章 动态规划 147

6.1动态规划概述 147

6.1.1动态规划的概念 147

6.1.2动态规划实施步骤 149

6.2 0-1背包问题 150

6.2.1一般0-1背包问题 150

6.2.2二维约束0-1背包问题 153

6.3西瓜分堆 156

6.4凸n边形的三角形划分 158

6.5最长子序列 160

6.5.1最长非降子序列 160

6.5.2最长公共子序列 163

6.6插入乘号问题 165

6.7数阵中的最优路径 167

6.7.1三角数阵中的最大路径 167

6.7.2矩阵中的最大路径 169

6.8动态规划设计小结 172

习题6 172

第7章 贪心算法 174

7.1贪心算法概述 174

7.1.1贪心算法的概念 174

7.1.2贪心算法的理论基础 175

7.2背包问题 176

7.2.1可拆背包问题 176

7.2.2 0-1背包问题 178

7.3删数字问题 179

7.4埃及分数式 182

7.4.1选择最小分母构建 182

7.4.2贪心选择范围的扩展 184

7.5数列操作与极差 185

7.5.1数列操作 185

7.5.2数列操作优化 187

7.5.3数列极差 188

7.6哈夫曼树及其应用 190

7.6.1哈夫曼树 190

7.6.2哈夫曼编码 193

7.7贪心算法应用小结 196

习题7 197

第8章 模拟 199

8.1模拟概述 199

8.1.1模拟分类 199

8.1.2竖式运算模拟 202

8.2乘数探求 203

8.2.1积为若干个1构成 203

8.2.2积为若干个2014构成 204

8.2.3积为任意指定构成 205

8.3特殊数积 206

8.3.1 01串积 206

8.3.2二部数积 209

8.4尾数前移问题 213

8.4.1限1位尾数前移 213

8.4.2多位尾数前移 215

8.5圆周率计算 218

8.5.1蒙特卡罗模拟计算 218

8.5.2指定高精度计算 219

8.6模拟发桥牌 221

8.7泊松分酒 223

8.8模拟应用小结 226

习题8 227

第9章 算法的综合应用与优化案例 228

9.1幂积序列 228

9.1.1双幂积枚举设计 228

9.1.2双幂积递推设计 230

9.1.3多幂积拓广 233

9.2高斯皇后问题 234

9.2.1高斯八皇后问题 235

9.2.2 n皇后问题 236

9.2.3皇后全控棋盘 238

9.3翻转硬币 241

9.3.1 m×9矩阵枚举设计 241

9.3.2 m×n矩阵回溯设计 247

9.3.3大规模矩阵贪心设计 251

9.4最优复杂路径 257

9.4.1三角数阵中的最小路径 257

9.4.2矩阵迷宫中的最小通道 260

9.5马步遍历与哈密顿圈 263

9.5.1马步遍历 263

9.5.2马步型哈密顿圈 268

9.5.3组合型哈密顿圈 272

9.6算法综合应用小结 277

习题9 278

附录A 在VC++ 6.0环境下运行C程序方法简介 280

附录B C常用库函数 284

参考文献 288