从零开始学算法(基于Python)
  • 推荐0
  • 收藏0
  • 浏览338

从零开始学算法(基于Python)

张启玉 (作者) 

  • 书  号:978-7-121-42241-6
  • 出版日期:2022-01-06
  • 页  数:332
  • 开  本:16(185*235)
  • 出版状态:上市销售
  • 维护人:高洪霞
纸质版 ¥109.00
本书的目的是帮助初学者掌握编程中的基础算法,并通过Python语言进行实战演练,通过即学即练的方式掌握这些经典算法,让读者真正体会算法的美妙,成为读者学习算法的领路人。
本书分为8章,涵盖的主要内容有算法之美,通过生活中的例子学习算法;贪心算法,选择当前最优的方案;分而治之算法,将复杂的问题拆分为简单的问题;树算法,围绕树结构的各种算法;图算法,围绕图结构的各种算法;动态规划,一种求解最优问题的强大工具;回溯法,深度优先遍历问题的解空间;分支限界法,广度优先遍历问题的解空间。
内容全面:涵盖程序员需要掌握的7种类别算法
化繁为简:列举30个趣味故事,提升阅读乐趣
实例驱动:每个算法都配有Python实例,即学即练
前言
这个技术有什么前途
随着计算机编程人员的不断增多,公司面试要求也越来越高,而算法无疑是面试官最喜欢考察的内容之一,学会算法是面试者或程序员应具备的基本能力;在面试的过程中,面试官通常也会考查面试者的编程能力。现在最流行的编程语言无疑是Python,本书不仅帮助初学者掌握算法,而且通过Python语言进行实战演练,让读者在理解算法的同时掌握Python,提升读者的综合竞争力。
笔者的使用体会
笔者也是从学生时代一路走来的,深知算法对编程者的重要性,也知道对于一名普通的初学者来说,算法入门多么不容易。算法并不神秘,算法就在我们身边,我们的吃喝住行样样离不开算法,我们吃的饭菜的烹饪顺序,喝的饮料的配方,房子里使用的扫地机器人的扫地路径,开车规划的最短路线等,都充斥着大量美妙的算法。算法种类繁多,给人“乱花渐欲迷人眼”的感觉,让很多初学者望而却步。其实算法本质上是有规律可循的,掌握这些规律,就会有一种“初极狭,才通人,复行数十步,豁然开朗”的感觉。笔者愿意把自己对算法的理解和掌握的规律分享给读者,希望读者通过本书能对算法也有一种“豁然开朗”的感觉,真正体会到算法的美妙。
本书的特色
本书描述的都是算法中的一些经典问题、经典解法,读者在学习的时候往往会惊叹这些算法设计得巧妙,会思考这些算法是怎么被想到的。其实这些算法都经过了严格的数学证明,但是证明过程对于初学者来说很难理解,如果深挖下去,不但会花费很多时间,而且还会把自己绕进去。本书从实际出发,省略掉令人乏味的数学证明,通过形象生动的图解演示整个算法过程,目的是让读者形象地了解算法的整个运行过程,加深记忆。再遇到类似问题,读者可以像求解数学题一样,触类旁通,用已经掌握的经典算法解决遇到的新问题。求解问题流程如下图所示。

求解问题流程
本书不仅描述算法的流程,而且还配以大量的Python实战演练,因为算法的设计和实现不应该被分割。有些面试者在面试的时候,可以将算法的原理讲得头头是道,但是一旦面试官让其将算法通过程序实现出来,就会出现无法下笔或者实现出来的程序和自己设计的算法不一致的情况。这主要是因为算法从设计到实现还需要一个大量训练的过程,如果只是训练算法的设计而忽略了算法的实现,那么对于程序员来说就相当于跛着脚走路,所以我建议初学者在理解算法以后要进行大量的实际编程,在编程中领悟算法。本书基于以上观点,在介绍完算法以后,会配以可执行的程序,通过程序的实际结果来验证算法的正确与否,让读者在理解算法的同时进行实战训练,加深对算法的理解,填补算法设计和算法实现之间的沟壑。
本书主要内容
本书主要讲解了7种常用的算法,分别是贪心算法、分而治之算法、树算法、图算法、动态规划算法、回溯法和分支限界法。
? 贪心算法。“贪心”又名“贪婪”,是求解最优化问题的一种算法,在求解最优问题时,贪心算法是最直观和最容易理解的。事物是具有两面性的,当前的最优并不一定是最终结果的最优,所以贪心算法并不能保证有最佳答案,但是常常可以帮助我们得到接近最佳答案的答案。
? 分而治之算法。顾名思义,先“分”而后“治”,“分”就是将整体划分成部分,“治”就是先求解部分问题,每个部分问题都解决了,整体也就解决了,“天下难事,必作于易;天下大事,必作于细”,只要事物达到了一定的规模,就需要不断地拆分,然后求解。
? 树算法。树结构是一个非常重要的数据结构,树结构在现实生活中随处可见,如家谱、公司组织结构、操作系统的目录等,围绕着树结构也有各种各样的算法,掌握这些算法以后处理树结构问题就可以得心应手。
? 图算法。图结构也是一个非常重要的数据结构,图结构在现实生活中也随处可见,如城市的交通轨道、人际关系、互联网等,围绕着图结构也有各种各样的算法,掌握这些算法以后处理图结构问题也就可以得心应手了。
? 动态规划算法。动态规划算法是比贪心算法更加强大、更通用的求解最优化问题的工具。在用动态规划算法对问题求解时,从整体最优上加以考虑是“目光长远”的,其从最终结果的最优解不断反推前面决策的最优。人们一旦学会了动态规划算法,无疑就掌握了一种求解最优问题的利器。
? 回溯法。通过深度优先搜索对待选解决方案进行系统的检查,在搜索的过程中去除不必要的搜索,极大地减少了程序的整个搜索时间,保证了在有限的时间内找到问题的答案。
? 分支限界法。通过广度优先搜索对待选解决方案进行系统的检查,在搜索的过程中去除不必要的搜索,极大地减少了程序的搜索时间,保证了在有限的时间内找到问题的答案。
本书读者对象
? 算法初学者
? Python程序员及其他编程爱好者
? 各计算机专业的大中专院校学生
? 需要算法入门工具书的人员
? 其他对算法有兴趣的人员

目录

目录
第1章 算法之美 1
1.1 生活中的算法——猜数游戏 1
1.1.1 好玩的猜数游戏 2
1.1.2 游戏的秘密——二分搜索技术 2
1.1.3 猜数游戏算法实现 4
1.2 算法的指标——空间复杂度和时间复杂度 6
1.2.1 时间复杂度 6
1.2.2 空间复杂度 9
1.3 经典算法回顾——排序算法 10
1.3.1 冒泡排序 10
1.3.2 简单选择排序 14
1.3.3 直接插入排序 19
1.4 怎样才能学好算法 23
第2章 贪心算法 24
2.1 短浅的眼光——贪心 24
2.1.1 适当的贪心——坏事变好事 25
2.1.2 过度贪心——赔了夫人又折兵 25
2.1.3 为贪心加上限制 25
2.2 美丽心灵——哈夫曼编码 26
2.2.1 认识哈夫曼编码 26
2.2.2 如何设计哈夫曼编码 27
2.2.3 哈夫曼编码算法实现 33
2.3 带你去旅行——单源最短路径 36
2.3.1 如何最快到朋友家做客 36
2.3.2 从最短的第一条路开始分析 37
2.3.3 找到抵达朋友家的最短路径 38
2.3.4 Dijkstra算法实现 44
2.4 选择困难症——背包问题 46
2.4.1 如何装沙子赚更多的钱 47
2.4.2 海盗的智慧 47
2.4.3 背包问题算法实现 50
2.5 搬家师傅的烦恼——集装箱装载问题 52
2.5.1 如何装更多的物品 53
2.5.2 搬家师傅的十年经验 53
2.5.3 装载问题算法实现 55
第3章 分而治之算法 58
3.1 纵横捭阖,各个击破——分而治之 58
3.1.1 分而治之——把复杂的事情简单化 59
3.1.2 可分可治,缺一不可 59
3.1.3 合久必分,分久必合——治而合之 60
3.2 真币和假币——伪币问题 61
3.2.1 可恶的假币 62
3.2.2 先对一半的硬币进行考虑 62
3.2.3 找出硬币的规律 64
3.3 再谈排序算法(1)——合并排序 66
3.3.1 如何将分而治之思想应用到合并排序上 67
3.3.2 先对一半的数字进行考虑 67
3.3.3 合并排序算法实现 70
3.4 再谈排序算法(2)——快速排序 74
3.4.1 如何将分而治之思想应用到快速排序上 74
3.4.2 找到一个“分”的中心 75
3.4.3 快速排序算法实现 79
3.4.4 排序算法总结 81
3.5 累人的比赛——循环赛日程安排 82
3.5.1 最公平的比赛 82
3.5.2 如何设计循环赛 83
3.5.3 找出循环赛的排列规律 86
第4章 树算法 89
4.1 生活中的“树” 89
4.1.1 炎黄子孙,生生不息 90
4.1.2 学校的组织结构 90
4.1.3 操作系统的目录结构 91
4.2 一叶一菩提——二叉树的遍历 92
4.2.1 什么是二叉树 92
4.2.2 二叉树的前序遍历 92
4.2.3 二叉树的中序遍历 97
4.2.4 二叉树的后序遍历 102
4.2.5 二叉树的平层遍历 107
4.3 重建家谱图——二叉树的还原 111
4.3.1 什么是二叉树的还原 112
4.3.2 前序遍历和中序遍历还原家谱图 113
4.3.3 中序遍历和后序遍历还原家谱图 118
4.4 十年树木,百年树人——二叉树的高度 123
4.4.1 什么是树的高度 123
4.4.2 在树的遍历基础上增加高度信息 124
4.4.3 遍历树获得高度信息 126
4.5 寻根溯源——找到所有祖先结点 128
4.5.1 什么是树的祖先 128
4.5.2 在树的遍历基础上增加结点找到信息 129
4.5.3 遍历树获得所有祖先 131
第5章 图算法 134
5.1 生活中的“图” 134
5.1.1 城市的交通轨道 135
5.1.2 人与人之间的关系 136
5.1.3 互联网的连接 136
5.2 寻找所有的城市——有向图的遍历 137
5.2.1 什么是有向图 137
5.2.2 有向图的深度优先遍历 138
5.2.3 有向图的广度优先遍历 144
5.3 最短的管道——Kruskal算法 149
5.3.1 如何铺设最短的管道 149
5.3.2 什么是最小生成树 150
5.3.3 Kruskal算法的贪心思想 151
5.3.4 Kruskal算法实现 156
5.4 再谈最短的管道——Prim算法 158
5.4.1 基于管道的边和结点贪心的区别 159
5.4.2 Prim算法的贪心思想 159
5.4.3 Prim算法实现 162
5.5 多源最短路径——Floyd算法 164
5.5.1 朋友之间相互访问的最短路径 164
5.5.2 自上而下分析朋友之间的最短路径 165
5.5.3 自下而上迭代朋友之间的最短路径 166
5.5.4 Floyd算法实现 172
第6章 动态规划算法 176
6.1 长远的眼光——动态规划 176
6.1.1 时间倒流,改变历史 177
6.1.2 慎用贪心算法 177
6.1.3 强者恒强,弱者恒弱——最优子结构 178
6.2 智能的语言翻译——编辑距离 178
6.2.1 设计语言翻译系统 179
6.2.2 考虑最后一次编辑情况 180
6.2.3 自下而上进行距离编辑 186
6.3 智能的电梯——电梯优化 196
6.3.1 设计智能电梯 196
6.3.2 先考虑最后一次电梯停留的情况 197
6.3.3 自下而上计算电梯的停留过程 200
6.4 名字的相似度——最长公共子序列 208
6.4.1 外国人名的相似度 208
6.4.2 考虑最后一个字符比较情况 209
6.4.3 自下而上进行距离编辑 213
第7章 回溯法 219
7.1 现代计算机的福音——回溯法 220
7.1.1 让猴子打出《莎士比亚全集》 220
7.1.2 一条路走到黑——深度遍历 221
7.1.3 乱花渐欲迷人眼——搜索中的剪枝 223
7.2 不能攻击的皇后——8个皇后问题 224
7.2.1 一山不容二虎 224
7.2.2 如何设计8个皇后的解向量 226
7.2.3 搜索过程中的剪枝 228
7.3 绝望的小老鼠——迷宫中的小老鼠 241
7.3.1 上帝视角帮助小老鼠 241
7.3.2 小老鼠如何进行搜索 242
7.3.3 小老鼠的出逃之路 248
7.4 再谈0/1背包问题 253
7.4.1 背包问题回顾 253
7.4.2 还可以使用贪心算法求解吗 253
7.4.3 通过搜索求解背包问题 255
7.5 再谈集装箱装载问题 262
7.5.1 集装箱装载问题回顾 263
7.5.2 使用贪心算法求解而存在的问题 263
7.5.3 通过搜索求解装载问题 264
第8章 分支限界法 276
8.1 一步一个脚印——分支限界 277
8.1.1 步步为营——广度遍历 277
8.1.2 剪掉没有营养的分支 279
8.1.3 条条大路通罗马——和回溯法的区别 280
8.2 再谈迷宫中的小老鼠问题 281
8.2.1 迷宫中的小老鼠问题回顾 281
8.2.2 使用分支限界思路规划小老鼠的路径 283
8.2.3 小老鼠的出逃之路 287
8.3 三谈0/1背包问题 291
8.3.1 0/1背包问题回顾 292
8.3.2 使用分支限界的思路装船 294
8.3.3 背包的搜索过程 300
8.4 三谈集装箱装载问题 305
8.4.1 集装箱装载问题回顾 305
8.4.2 使用分支限界的思路装载集装箱 307
8.4.3 集装箱的装载过程 314

读者评论

相关博文