计算机常用算法与程序设计案例教程(第3版)

第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拆分为连续正整数之和14
1.3.3统计n!尾部零16
1.4算法与程序设计18
1.4.1算法与程序18
1.4.2结构化程序设计23
习题125第2章枚举27
2.1枚举概述27
2.2素数与合数28
2.2.1区间素数搜索29
2.2.2探求合数世纪30
2.2.3合数的质因数分解32
2.3解方程34
2.3.1佩尔方程35
2.3.2超越方程36
2.4解不等式38
2.4.1分数不等式38
2.4.2代数和不等式39
2.5求*值42
2.5.1基于素数的代数和42
2.5.2整数的因数比43
2.6整数拆分45
2.6.1简单的整币兑零45
2.6.2拆分构建双和二组48
2.7数式探求50
2.7.1逆序乘积式50
2.7.2完美综合式51
2.8趣味数阵54
2.8.1素数幻方54
2.8.2和积三角形57
2.9枚举应用小结59
习题262第3章递推64
3.1递推概述64
3.1.1递推算法64
3.1.2递推实施步骤与描述65
3.2超级素数搜索66
3.3递推数列69
3.3.1摆动数列70
3.3.2分数数列71
3.4幂序列72
3.4.1双幂序列72
3.4.2幂积序列74
3.5数阵与网格79
3.5.1杨辉三角79
3.5.2交通方格网81
3.6整数划分问题83
3.6.1整数划分递推设计83
3.6.2整数划分递推优化84
3.7增强型整币兑零86
3.8猴子爬山89
3.8.1简单案例的具体递推89
3.8.2一般情形的分级递推90
3.9递推应用小结92
习题393第4章递归95
4.1递归概述95
4.2排队购票98
4.3汉诺塔问题99
4.3.1求移动次数100
4.3.2展示移动过程101
4.4旋转数阵102
4.4.1双转向旋转方阵102
4.4.2m行n列顺转矩阵105
4.5快速排序与选择107
4.5.1快速排序107
4.5.2分区交换选择110
4.6排列组合的实现112
4.6.1实现排列A(n,m)112
4.6.2实现组合C(n,m)114
4.6.3复杂排列116
4.7整数的拆分118
4.7.1拆分零数取自连续区间118
4.7.2拆分零数取自指定整数119
4.8递归应用小结121
习题4124第5章回溯法125
5.1回溯法概述125
5.1.1回溯的概念125
5.1.2回溯描述125
5.2桥本分数式与10数字分数式129
5.2.1桥本分数式129
5.2.210数字分数式131
5.3直尺与串珠133
5.3.1古尺神奇133
5.3.2数码串珠135
5.4逐位整除数137
5.5环序列141
5.5.1素数和环141
5.5.2德布鲁金环142
5.6伯努利装错信封问题144
5.6.1装错信封问题145
5.6.2特殊错位探索148
5.7别出心裁的情侣拍照问题150
5.7.1逐位安排与回溯150
5.7.2成对安排与回溯152
5.8回溯应用小结153
习题5156第6章动态规划157
6.1动态规划概述157
6.1.1动态规划的概念157
6.1.2动态规划实施步骤158
6.2*长子序列探索159
6.2.1*长非降子序列159
6.2.2*长公共子序列162
6.3*优路径搜索164
6.3.1点数值三角形的*优路径165
6.3.2边数值矩形的*优路径166
6.4装载问题169
6.501背包问题173
6.5.1一般01背包问题173
6.5.2二维约束01背包问题177
6.6凸n边形的三角形划分179
6.7插入乘号问题181
6.8动态规划应用小结184
习题6186第7章贪心算法188
7.1贪心算法概述188
7.2删数字问题190
7.3埃及分数式192
7.3.1选择*小分母构建193
7.3.2贪心选择范围的扩展194
7.4可拆背包问题195
7.5数列操作与极差197
7.5.1数列操作197
7.5.2数列操作优化198
7.5.3数列极差200
7.6哈夫曼树及其应用202
7.6.1哈夫曼树202
7.6.2哈夫曼编码204
7.7贪心算法应用小结207
习题7208第8章分支限界法210
8.1分支限界法概述210
8.2搜索迷宫*短通道211
8.2.1矩阵迷宫212
8.2.2三角迷宫217
8.3增强型装载问题220
8.4增强型01背包问题223
8.5新奇的八数码游戏226
8.5.1移动常规设计227
8.5.2数组优化设计231
8.6分支限界法应用小结234
习题8235第9章模拟236
9.1模拟概述236
9.1.1模拟分类236
9.1.2竖式运算模拟239
9.2精彩乘积式241
9.2.1积由指定一个整数重复构成241
9.2.2积由指定两个整数构成245
9.2.3二部数积(ACM背景)249
9.3尾数前移问题252
9.3.1限1位尾数前移252
9.3.2多位尾数前移254
9.4阶乘幂与排列组合数的计算255
9.5高精度计算圆周率257
9.6模拟发桥牌261
9.7泊松分酒问题263
9.8模拟应用小结266
习题9267第10章算法的综合应用268
10.1高斯八皇后问题268
10.1.1高斯八皇后问题概述268
10.1.2n皇后问题270
10.1.3皇后全控棋盘问题274
10.2翻转硬币游戏277
10.2.1翻转m×9矩阵278
10.2.2翻转m×n矩阵280
10.2.3大规模矩阵求解283
10.3马步遍历与哈密顿圈286
10.3.1马步遍历286
10.3.2马步型哈密顿圈293
10.3.3组合型哈密顿圈297
10.4综合应用小结304
习题10304附录A部分习题求解提示306附录B在VC 6.0环境下运行C程序方法简介323附录CC语言常用库函数327参考文献331