计算机常用算法与程序设计案例教程（第3版）_杨克昌_9787302652847

本书遵循精选案例，面向设计，深入浅出，注重能力培养的宗旨，以案例形式实现算法与程序设计教学。本书选取枚举、递推、递归、回溯、动态规划、贪心算法、分支限界法与模拟等常用算法，并精选应用各算法设计求解的典型案例。书中每个案例求解，从案例提出到算法设计与程序实现，从案例结果显示到算法改进与程序优化，环环相扣，融为一体，力求算法理论与实际应用相结合、算法与程序相统一，突出算法在解决实际案例中的核心地位与引导作用。
书中所有案例求解均给出详细的算法设计提要与完整的C程序清单，所有程序均在VC 6.0编译通过，所有源代码均可从指定网站下载。
本书可作为高等院校计算机及相关专业算法设计与分析程序设计基础与应用等课程的教材，也可供各类计算机程序设计竞赛与计算机编程培训参考。

计算机常用算法与程序设计案例教程(第3版)前言前言
计算机算法与程序设计是计算机科学与技术的核心内容，是大学计算机相关专业的重要专业基础课。通过对现有计算机专业算法设计与分析教学的调研分析，很多同学对学过的算法思路不明了，描述不清楚，设计不到位，无法应用算法设计程序解决一些常见的实际问题。造成这一局面的重要原因之一是缺少适合计算机本科层次的算法与程序设计教材。
一般现有算法设计与分析教材在算法选取上贪多求全、贪广求深，混杂一些难度大、理论深、少有应用的算法罗列。同时，在讲授算法时存在对算法的抽象描述多,应用算法设计解决实际问题少等偏差，造成算法与程序设计脱节，算法理论与实际应用脱节，不利于学生应用算法与程序设计解决实际问题能力的提高。
为此，我们对《计算机程序设计经典题解》(清华大学出版社, 2007)、《至美C程序设计》(中国水利水电出版社，2016)与《计算机常用算法与程序设计教程》(第2版, 人民邮电出版社, 2017)等进行优化整合，推出适合本科算法与程序设计教学实际的案例教程。
本书遵循精选案例，面向设计，深入浅出，注重能力培养的宗旨，在常用算法典型案例的选取与深度的把握上，在算法理论与案例求解的结合上进行精心设计，力图适合高校计算机本科教学目标与知识结构的要求。本书具有以下5个特色。
1. 首创案例形式实现算法与程序设计教学
学习算法与程序设计是为了培养提高学生应用算法与程序设计解决实际问题的能力，算法与程序设计课程教学无疑是最适宜以案例形式来实现的。通过实际案例的求解见证算法设计的神奇与功效，实现以典型案例支撑算法设计，以算法设计指导案例求解的良性循环。
采用案例形式实现算法与程序设计教学在全国属首创。对每个案例求解，从案例提出到算法设计、从程序实现到显示运行结果，从算法分析到程序设计优化，环环相扣，融为一体，让学生看得见、摸得着、学得会、用得上，从而收到立竿见影、举一反三的效果。
2. 注重常用算法的选取与组织
在常用算法的选取上克服贪多求全、贪广求深，去除若干难度大、理论深、少有应用的算法罗列，结合本科教学目标与应用实际，选取枚举、递推、递归、回溯、动态规划、贪心算法、分支限界法与模拟等常用算法。注意到分支限界是一种以广度优先搜索最优解的基本算法，本版将分支限界法列入常用算法之中。
特别指出的是，模拟算法中的竖式运算模拟是总结推广数论高精度计算的创新成果。
对精选的各种常用算法，在介绍算法的基本理论与设计思路基础上，从实际案例的求解入手，重点突出该算法的基本思路、设计规范与实施步骤，列出程序清单，显示案例求解结果，达到清晰明了、水到渠成的效果。
3. 注重典型案例的精选与提炼
针对选取的每一种常用算法，精选典型的实际应用案例，包括基本的数值求解、常规的数据处理、有趣的智力测试、巧妙的模拟探索，既有引导入门的基础案例，也有难度较大的综合案例；既有历史悠久的经典名题，也有构思巧妙的新创趣题，难度适宜，深入浅出。
培养学生的学习兴趣，激发学生的学习热情，不是一两句空洞说教所能奏效的，必须通过一系列有趣的实际案例来引导。本书针对所精选的常用算法，设计出初等难度基础型、中等难度提升型、较高难度综合型3种梯度的实际案例。这些案例的精选与提炼，有利于提高学生学习算法与程序设计的兴趣，有利于学生在计算机实际应用方面开阔视野，使之在算法思路的开拓与设计技能的运用上有一个深层次的锻炼与提高。其中，难度较大的综合案例可作为相应课程的课程设计选用。
4. 注重算法设计与程序实现的紧密结合
算法与程序实际上是一个统一体，不应该也不可能将它们对立与分割。本书对每一种常用算法的设计规范，具体落实到实际案例求解的各个环节: 有算法设计提要，有程序实现清单，有运行示例显示，有算法改进与程序优化，环环相扣，融为一体。通过算法设计与程序实现的紧密结合，突出算法在解决实际案例中的核心地位与引导作用，不断加深对所学算法的理解和领悟，切实提升应用所学算法解决实际问题的能力。
本书采用功能丰富、应用面广、高校学生使用率最高的 C语言描述算法、编写程序。为使用方便，所有程序均在VC 6.0编译通过。
5. 注重算法改进与程序优化
本书对一些典型案例应用多种不同的算法设计，编写不同表现形式与设计风格的程序，充分体现了算法与程序设计的灵活性和多样性。
算法与程序设计都不是一成不变的，可以实施多层次全方位的变通，变通出成果，变通长能力。算法改进与程序优化的过程，既是提高案例求解效率的过程，也是算法设计能力培养与提高的过程，更是优化意识与创新能力增强的过程。
为方便算法设计练习与查阅，附录中提供部分习题求解提示，介绍在VC 6.0环境下运行C程序的方法，并列出C语言常用函数。书中的所有案例源程序与部分习题源代码均可在指定网站下载。
在书稿的编写与修订过程中，湖南理工学院教务处及王岳斌教授、严权峰教授、周持中教授等给予了多方面支持与帮助，笔者在此一并深表感谢。
尽管每个案例求解都经反复核实检查，每个求解程序都经多轮运行调试，因涉及内容较广，难免存在差错，恳请各位读者批评指正。

杨克昌2023年11月于岳阳南湖

第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翻转m9矩阵278
10.2.2翻转mn矩阵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

我要评论