计算机常用算法与程序设计案例教程

   

第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
习题120

第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
习题253

第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
习题383

第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
习题4115

第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
习题5150

第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
习题6185

第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
习题7208

第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
习题8231

第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
习题9267附录268
附录a 部分习题求解提要268
附录b 在vc++6.0环境下运行c程序方法简介290
附录c c常用库函数295参考文献299