计算机常用算法与程序设计案例教程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.3 算法与程序设计 13

1.3.1 算法与程序 13

1.3.2 结构化程序设计 18

习题1 20

第2章 枚举 22

2.1 枚举概述 22

2.2 统计与求和 23

2.2.1 指定特殊整数 23

2.2.2 最简真分数 25

2.3 解方程 26

2.3.1 解佩尔方程 26

2.3.2 解超越方程 28

2.4 解不等式 30

2.4.1 分数不等式 30

2.4.2 代数和不等式 31

2.5 求最值 34

2.5.1 基于素数的代数和 34

2.5.2 整数的因数比 35

2.6 数组与数列 36

2.6.1 双和数组 36

2.6.2 基于2x+3y的递推数列 38

2.7 数式探求 39

2.7.1 逆序乘积式 39

2.7.2 完美综合式 40

2.8 趣味数阵 43

2.8.1 素数幻方 43

2.8.2 和积三角形 46

2.9 枚举应用小结 48

习题2 53

第3章 递推 55

3.1 递推概述 55

3.1.1 递推算法 55

3.1.2 递推实施步骤与描述 56

3.2 递推数列 58

3.2.1 摆动数列 58

3.2.2 分数数列 59

3.3 幂序列 60

3.3.1 双幂序列 60

3.3.2 幂积序列 62

3.4 数阵探索 67

3.4.1 杨辉三角 67

3.4.2 折叠方阵 69

3.5 整数划分问题 71

3.5.1 整数划分递推设计 71

3.5.2 整数划分递推优化 73

3.6 水手分椰子问题 74

3.6.1 水手分椰子 74

3.6.2 n个水手分椰子 77

3.7 猴子爬山 79

3.7.1 简单案例的具体递推 79

3.7.2 一般情形的分级递推 80

3.8 递推应用小结 82

习题3 83

第4章 递归 85

4.1 递归概述 85

4.2 排队购票 87

4.3 汉诺塔问题 89

4.3.1 求移动次数 90

4.3.2 展示移动过程 91

4.4 旋转数阵 92

4.4.1 双转向旋转方阵 92

4.4.2 m行n列顺转矩阵 95

4.5 快速排序与选择 97

4.5.1 快速排序 97

4.5.2 分区交换选择 100

4.6 排列组合的实现 102

4.6.1 实现排列A（n,m） 102

4.6.2 实现组合C（n,m） 105

4.6.3 实现复杂排列 107

4.7 整数的拆分 109

4.7.1 拆分零数取自连续区间 109

4.7.2 拆分零数取自指定整数 111

4.8 递归应用小结 112

习题4 115

第5章 回溯法 117

5.1 回溯法概述 117

5.1.1 回溯的概念 117

5.1.2 回溯描述 117

5.2 桥本分数式 122

5.2.1 桥本分数式概述 122

5.2.2 10数字分数式 124

5.3 直尺与串珠 125

5.3.1 古尺神奇 126

5.3.2 数码串珠 128

5.4 逐位整除数探索 130

5.4.1 高逐位整除数 130

5.4.2 低逐位整除数 132

5.5 环序列 134

5.5.1 素数和环 134

5.5.2 德布鲁金环 136

5.6 装错信封问题 138

5.6.1 伯努利装错信封问题 138

5.6.2 特殊错位探索 141

5.7 别出心裁的情侣拍照 144

5.7.1 逐位安排与回溯 144

5.7.2 成对安排与回溯 146

5.8 回溯应用小结 148

习题5 150

第6章 动态规划 152

6.1 动态规划概述 152

6.1.1 动态规划的概念 152

6.1.2 动态规划实施步骤 153

6.2 最长子序列探索 154

6.2.1 最长非降子序列 154

6.2.2 最长公共子序列 157

6.3 最优路径搜索 160

6.3.1 点数值三角形的最优路径 160

6.3.2 边数值矩形的最优路径 162

6.4 装载问题 165

6.5 0-1背包问题 169

6.5.1 一般0-1背包问题 169

6.5.2 二维约束0-1背包问题 173

6.6 插入乘号问题 178

6.6.1 动态规划求解 178

6.6.2 基于组合枚举求解 181

6.7 动态规划应用小结 182

习题6 185

第7章 贪心算法 186

7.1 贪心算法概述 186

7.2 删数字问题 187

7.3 埃及分数式 190

7.3.1 选择最小分母构建 190

7.3.2 贪心选择范围的扩展 192

7.4 可拆背包问题 193

7.5 数列操作与极差 195

7.5.1 数列操作 195

7.5.2 数列操作优化 196

7.5.3 数列极差 198

7.6 哈夫曼树及其应用 201

7.6.1 哈夫曼树 201

7.6.2 哈夫曼编码 204

7.7 贪心算法应用小结 207

习题7 208

第8章 模拟 210

8.1 竖式乘除模拟 210

8.1.1 竖式除模拟 210

8.1.2 竖式乘模拟 211

8.2 乘数探求 211

8.2.1 积为若干个1构成 212

8.2.2 积为若干个2011构成 213

8.2.3 积的任意指定构成 214

8.3 尾数前移问题 215

8.3.1 限1位尾数前移 215

8.3.2 多位尾数前移 217

8.4 阶乘幂与排列组合数的计算 218

8.5 圆周率π的高精度计算 220

8.6 蒙特卡罗模拟计算 222

8.7 模拟发桥牌 224

8.8 泊松分酒 227

8.9 模拟应用小结 230

习题8 231

第9章 算法的综合应用 232

9.1 最大子段和问题 232

9.1.1 序列的最大子段和 232

9.1.2 环序列的最大子段和 235

9.2 高斯皇后问题 238

9.2.1 高斯八皇后问题 238

9.2.2 n皇后问题 240

9.2.3 皇后全控棋盘问题 243

9.3 马步遍历与哈密顿圈 248

9.3.1 马步遍历 249

9.3.2 马步型哈密顿圈 256

9.3.3 组合型哈密顿圈 260

9.4 算法的综合应用小结 266

习题9 267

附录 268

附录A 部分习题求解提要 268

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

附录C C常用库函数 295

参考文献 299