算法设计实战

算法设计实战 50 讲

王晓华 · 《算法的乐趣》作者

6530人已买
详情
目录(51)

算法为什么难学?

算法在程序中扮演着非常重要的角色,有人将数据结构比喻为程序的骨架,将算法比喻为程序的灵魂,这一点也不为过。正是因为这一点,很多朋友都立志要学好算法,但是我常常看到各种抱怨,比如“看了半年《算法》这本书,才看了几十页”,再比如“四年了,还是没有啃完《算法导论》”。出现这种情况的主要原因有两个:

  1. 算法纷繁复杂、知识点多,没有一种放之四海而皆准的通用规则,很难一下子从总体上掌握全貌;
  2. 一些算法虽然有常用的设计模式,但是不同的问题有不同的数学模型,需要设计好数学模型才能带入算法模式进行求解,然而设计数学模型对新手来说通常是个很高的门槛。

如何用算法解决实际问题?

人们设计各种算法的目的是解决现实中的问题,虽然各种算法的实现五花八门,但是设计算法却有一些通用的方法或思想(也有的资料将其称为算法设计模式)。归纳起来,这些常见的算法设计方法有迭代法、穷举搜索法、分支界限法(剪枝法)、递推法、递归法、回溯法、分治法、贪婪法和动态规划法等。

本专栏选择了 35 个简单且实用的算法实例,这些算法实例基本覆盖了各种算法比赛中经常出现的题目以及生活中常见的算法实现。每个算法实现都将讲解的侧重点放在各种算法的设计方法在算法中的体现,通过一个个算法例子,来引导大家掌握常见的算法设计思想。

除此之外,在算法实现的过程中,还会详细介绍针对各个问题的建模过程,使读者能够举一反三,学会如何将文字描述的问题抽象为算法能够使用的数据模型。总之,本专栏的目的不是学会这些算法,而是通过学习这些算法的实现,掌握算法设计的方法,以后遇到类似的问题,可以自己设计并实现解决问题的算法。

你将学到

  • 35 个经典算法案例和建模过程
  • 如何自己动手设计算法实现
  • 将算法原理翻译成算法代码的常用技巧
  • 如何将实际问题抽象为的数学模型

专栏大纲

本专栏前半部分根据常见的算法题目,重点介绍迭代、穷举和动态规划三个主题,三个主题共计 18 个算法实例,基本上涵盖了上述所有算法设计方法和思想的应用。后半部分则通过 24 个有趣的算法实现,让大家理解算法的重要性,但重点仍然是各种算法设计思想的应用和如何设计适用于算法的数据模型。

本专栏的目的是培养大家解决实际问题的能力,每篇介绍一个算法问题,通过对这个问题的分析和解决,锻炼大家针对问题设计数据模型,并应用合适的算法思想设计出解决问题的算法实现的能力。 本专栏分为七大部分,共计 49 篇。

第一部分(第 3 ~ 9 篇):基础

这部分内容包含 7 篇,第 1 篇为算法基础内容,介绍了将问题抽象成数据建模的常用方法;第 2 ~ 6 篇介绍了 5 种常用的算法设计思想(模式),分析了各种算法模式的特点和使用时需要注意的要点,每种模式都用一到两个具体的算法做示例;第 7 篇介绍了一些基础算法和技巧,比如排序、单链表逆序和用数组存储树等小算法,作为本专栏开始之前的热身或开胃菜。

第二部分(第 10 ~ 12 篇):迭代和递推

这部分内容通过 3 个在数学领域常用的数值分析方法,介绍了迭代思想在算法设计中的应用,还包括如何将数学公式或文字描述的递推关系转化为数据模型的方法。

第三部分(第 13 ~ 21 篇):穷举搜索

这部分内容包含 9 篇,前 7 篇通过 7 个不同的算法实例,介绍了几种常见的穷举方法,比如线性数字类问题的穷举方法、树形空间的穷举方法、棋盘类游戏的常用穷举方法以及复杂问题的多重穷举和组合穷举方法,重点介绍了如何设计与穷举算法相适应的数据模型,以及用合理的数据模型简化算法实现的技巧。后两篇分别介绍了如何理解和设计递归函数,以及算法中浮点数处理的一些经验。

第四部分(第 22 ~ 29 篇):动态规划

这部分内容包含 8 篇,第 1 篇介绍了动态规划算法的常用设计思想和方法,后面 7 篇分别介绍了 7 个有趣的算法,其中有一些是算法比赛中出现过的题目,还有一些是动态规划的典型问题,既有简单的线性(一维)动态规划和二维动态规划问题,也有凸多边形的三角剖分、矩阵链乘这样的热点问题。

动态规划最重要的是划分阶段和确定状态(确定递推关系式),通过这些例子,可以了解如何建立问题对应的数据模型以及建立在数据模型上的递推关系式。掌握这些方法,再遇到动态规划类的问题时,就不会束手无策了。

第五部分(第 30 ~ 35 篇):图论

图论既是各种算法比赛中出题的“重灾区”,也是现实生活中很多有趣算法的理论基础,这部分内容选了 6 个有趣的算法,包括二分图的最大匹配、图的排序和关键路径、欧拉图、最大流等经典问题,讲解的重点仍然是各种算法设计的思想和建立数据模型。

第六部分(第 36 ~ 43 篇):游戏中常用的算法

这部分内容包含 8 篇,介绍了一些游戏中常用的有趣味算法,包括决策树、博弈树和行为树的搜索算法,涉及的内容包括穷举、递归和分支界限法等算法思想的应用。这些算法都是非常经典的,掌握这些算法思想,将有助于读者开阔思维、提升代码能力。

第七部分(第 44 ~ 49 篇):算法与应用

这部分内容介绍了 6 个算法,都是一些名声远扬的公开算法,不需要重新设计,学习这些算法的关键是如何根据实际的问题建立数据模型,然后套用算法解决问题。每种算法都有具体的实例,通过这些例子与算法原理相结合,不仅有助于理解算法,还可以了解到将这些算法应用到实践中常用的建模方法。

作者介绍

王晓华,毕业于华中科技大学,著有《算法的乐趣》一书。目前就职于中兴通讯,任职开发经理和资深软件工程师,主要工作是嵌入式通讯软件开发。精通 C 和 C++ 开发语言,以及算法设计、面向对象的软件设计和重构、测试驱动开发、敏捷与过程改进、Windows 内核文件系统、汇编语言、软件破解与保护、网络安全。

专家推荐

《算法设计实战 50 讲》展示有趣的问题、启发有趣的思路、归纳有趣的解法,是一门有趣的专栏。

——王益,百度美研 T10 架构师,百度深度学习系统 PaddlePaddle 的技术负责人

《算法设计实战 50 讲》是真正在训练读者解决问题的能力,而解决问题的能力,正是任何一家公司所需人才的最核心的技能。

——黄鑫(飞林沙),极光推送首席科学家

适宜人群

  • 软件开发人员
  • 编程和算法爱好者
  • 计算机专业的学生

订阅须知

  • 本专栏为订阅专栏,形式为“图文+音频”内容,共计 50 期。
  • 付费用户可享受文章永久阅读权限。
  • 本专栏为虚拟产品,一经付费概不退款,敬请谅解。
  • 本专栏可在 GitChat 服务号、App 及网页端 gitbook.cn 上购买,一端购买,多端阅读。

订阅福利

  • 订购本专栏可获得专属海报(在 GitChat 服务号领取),分享专属海报每成功邀请一位好友购买,即可获得 25% 的返现奖励,多邀多得,上不封顶,立即提现。

  • 提现流程:在 GitChat 服务号中点击「我-我的邀请-提现」。

  • 购买本专栏后,服务号会自动弹出入群二维码和暗号。如果你没有收到那就先关注微信服务号「GitChat」,或者加我们图上的小助手微信进行咨询。(入群方式可查看第 3 篇文末说明)。

购买须知

  • 本课程内容版权归北京码字科技发展有限公司独家所有,未经授权,不得转载。
  • 本课程为虚拟产品,一经付费概不退款,敬请谅解。
  • 添加 GitChat 助教俏俏(微信 ID: gitchat2025),加入免费技术交流群。
× 订阅 Java 精选频道
¥ 元/月
订阅即可免费阅读所有精选内容