算法与程序设计

图书标准信息

• 作者 杨建英
• 出版社 电子工业出版社
• 出版时间 2022-08
• 版次 1
• ISBN 9787121438950
• 定价 59.80元
• 装帧 其他
• 开本 16开
• 页数 232页
• 字数 459千字

【内容简介】

本书遵循“精选案例，面向设计，深入浅出，注重能力培养”的要求，以案例形式实现算法与程序设计教学，精选了穷举法、递推法、回溯法、分支限界法、递归法、分治法、贪心算法、动态规划法和随机算法等常用算法进行讲解，并给出了使用各算法求解的典型案例。对于每一个案例的求解，从问题提出到算法设计、从程序实现到算法复杂度分析，环环相扣，融为一体，力求理论与实际相结合、算法与程序相统一，突出算法在解决实际问题中的核心地位与引导作用。本书中的所有案例均给出算法设计要点与完整的C语言或者C++语言程序代码（均在VC++ 6.0上编译通过）。为方便教学，每章都附有习题，同时提供教学课件、习题答案、源代码等配套资源，读者可登录华信教育资源网（www.hxedu.com.cn）免费下载使用。本书既可作为高等院校计算机专业相关课程的教材，也可供IT从业人员和计算机编程爱好者参考使用。

【作者简介】

杨建英，硕士毕业于华南师范大学人工智能与模糊识别专业，目前在山西大学软件学院任教。山西CCF大会分会委员，山西大学计算机协会指导教师，山西大学软件应用协会指导教师，山西大学ACM-ICPC算法队指导老师，山西大学精英之英竞赛与科技创新团队指导老师。 参与多个国家自然科学基金青年基金项目，荣获山西省科技进步三等奖，“数据库原理与应用”获得山西省精品资源共享课程，出版《Vue.js企业开发实战》《Python快乐编程数据分析与实战》《C语言教程与等级考试》等多部图书。

【目录】

第1章　算法与程序设计简介1

1.1　初识算法1

1.1.1　算法的基本概念2

1.1.2　算法的描述4

1.1.3　算法设计的步骤7

1.1.4　算法的分类8

1.2　算法复杂度分析9

1.2.1　时间复杂度9

1.2.2　空间复杂度14

1.2.3　算法设计实例15

1.3　程序设计简介17

1.3.1　算法与程序18

1.3.2　结构化程序设计19

1.3.3　结构化程序设计实例20

习题21

第2章　穷举法23

2.1　穷举法概述23

2.1.1　穷举法的基本思想23

2.1.2　穷举法的实施步骤与算法描述23

2.2　整数搜索25

2.2.1　算24点游戏25

2.2.2　韩信点兵27

2.2.3　素数问题28

2.2.4　约瑟夫环问题29

2.2.5　火柴棒等式30

2.2.6　三色旗问题31

2.2.7　勾股数问题32

2.2.8　猜价格游戏33

2.3　分解与重组35

2.3.1　水仙花数35

2.3.2　回文数35

2.3.3　完数36

2.4　趣味数学37

2.4.1　百钱买百鸡问题37

2.4.2　搬砖问题38

2.4.3　鸡兔同笼问题38

2.4.4　数学灯谜39

2.5　解方程与不等式40

2.5.1　解二元一次方程40

2.5.2　解完美立方式40

2.5.3　解一元二次不等式41

2.6　数阵与图形42

2.6.1　杨辉三角形42

2.6.2　输出各种图形43

2.7　穷举设计的优化45

习题47

第3章　递推法48

3.1　递推法概述48

3.1.1　递推法的基本思想48

3.1.2　递推法的实施步骤与算法描述49

3.2　递推数列51

3.2.1　斐波那契数列和卢卡斯数列51

3.2.2　分数数列53

3.2.3　幂序列53

3.2.4　双关系递推数列54

3.2.5　储油点问题56

3.3　递推数阵57

3.3.1　累加和57

3.3.2　阶乘问题58

3.3.3　九九乘法表58

3.4　递推的其他应用59

3.4.1　猴子爬山问题59

3.4.2　整币兑零问题60

3.4.3　整数划分问题61

3.4.4　汉诺塔问题61

3.4.5　体重指数BMI62

3.4.6　求π的近似值63

3.4.7　求一元二次方程的根63

3.4.8　求三角形的面积64

3.4.9　存钱问题65

3.4.10　求最大公约数和最小公倍数66

习题67

第4章　回溯法68

4.1　回溯法概述68

4.1.1　回溯法的基本思想68

4.1.2　回溯法的实施步骤和算法描述69

4.2　回溯法的应用70

4.2.1　八皇后问题70

4.2.2　图的着色问题71

4.2.3　装载问题73

4.2.4　批处理作业调度75

4.2.5　符号三角形问题77

4.2.6　最大团问题78

4.2.7　旅行售货员问题80

4.2.8　电路板排列问题82

4.2.9　连续邮资问题84

4.2.10　圆排列问题86

4.2.11　桥本分数式88

4.2.12　素数环89

4.2.13　神奇古尺91

4.3　回溯设计的优化92

习题93

第5章　分支限界法94

5.1　分支限界法概述94

5.1.1　分支限界法的基本思想94

5.1.2　分支限界法的实施步骤和算法描述94

5.2　分支限界法的应用95

5.2.1　迷宫问题95

5.2.2　六数码问题98

5.2.3　旅行商问题101

5.2.4　背包问题104

5.3　回溯法与分支限界法的比较108

习题109

第6章　递归法110

6.1　递归法概述110

6.1.1　递归法的基本思想110

6.1.2　递归法的实施步骤和算法描述110

6.2　递归法的应用111

6.2.1　整数划分问题111

6.2.2　汉诺塔问题112

6.2.3　枚举排列问题113

6.2.4　用递归法求斐波那契数列114

6.2.5　排队买票问题115

6.2.6　猴子吃桃子问题116

6.2.7　RPG涂色问题117

6.2.8　二叉树的遍历118

6.3　回溯法与递归法的比较120

习题120

第7章　分治法121

7.1　分治法概述121

7.1.1　分治法的基本思想121

7.1.2　分治法的实施步骤和算法描述122

7.2　分治法的应用123

7.2.1　二分查找法123

7.2.2　大整数乘法125

7.2.3　斯特拉森矩阵乘法127

7.2.4　棋盘覆盖问题128

7.2.5　合并排序129

7.2.6　快速排序132

7.2.7　线性时间选择133

7.2.8　最近点对问题136

7.2.9　循环赛日程表137

7.3　递归转化139

7.3.1　一般的递归转非递归139

7.3.2　分治法中的递归转化141

习题143

第8章　贪心算法145

8.1　贪心算法概述145

8.1.1　贪心算法的基本思想145

8.1.2　贪心算法的实施步骤与算法描述145

8.2　活动安排问题146

8.3　田忌赛马148

8.4　背包问题149

8.5　覆盖问题151

8.5.1　区间覆盖问题151

8.5.2　最大不相交覆盖151

8.5.3　点覆盖151

8.6　教室调度问题153

8.7　最小生成树——Kruskal算法155

8.8　最小生成树——Prim算法157

8.9　哈夫曼编码160

8.10　教室分配问题164

8.11　最短路径——弗洛伊德算法166

8.12　最短路径——迪杰斯德拉算法169

8.13　均分纸牌172

8.14　最佳浏览路线问题173

8.15　机器调度问题175

8.16　钱币找零问题176

习题177

第9章　动态规划法178

9.1　动态规划法概述178

9.1.1　动态规划法的基本思想178

9.1.2　动态规划法的实施步骤与算法描述179

9.2　装载问题180

9.3　投资分配问题181

9.4　背包问题185

9.4.1　0-1背包问题185

9.4.2　二维0-1背包问题187

9.5　最长子序列探索188

9.5.1　最长非降子序列188

9.5.2　最长公共子序列（Longest Common Subsequence，LCS）190

9.6　最优路径搜索192

9.6.1　数字三角形最大路径和192

9.6.2　多源最短路径问题194

9.6.3　走方格问题197

9.6.4　邮资问题198

9.7　动态规划与其他算法的比较199

习题200

第10章　随机算法201

10.1　随机算法概述201

10.2　随机数201

10.2.1　随机生成数组元素202

10.2.2　随机生成数字204

10.2.3　随机生成计算题206

10.3　同余算法208

10.4　舍伍德算法209

10.5　蒙特卡罗算法211

10.5.1　用蒙特卡罗算法求π的值211

10.5.2　用蒙特卡罗算法求特殊图形的面积212

10.5.3　蒙特卡罗算法的优缺点及改进措施213

10.6　拉斯维加斯算法214

10.7　蒙特卡罗算法和拉斯维加斯算法的比较217

10.8　随机算法的优缺点217

习题217

附录A　不同算法的比较219

参考文献221