看看豆-提供优质正版电子书导购服务

书籍信息

算法的乐趣收藏本书

算法的乐趣

书籍导购

书籍介绍

编辑推荐

适读人群 :适合软件开发人员、编程和算法爱好者以及计算机专业的学生阅读
CSDN超人气博主、算法专栏达人王晓华力作
淋漓尽致展现算法本质,广泛涵盖常用算法结构及其应用
一本书玩转算法,尽享算法乐趣

内容简介

  算法之大,大到可以囊括宇宙万物的运行规律;算法之小,小到寥寥数行代码即可展现一个神奇的功能。算法的应用和乐趣在生活中无处不在:
  历法和二十四节气计算使用的是霍纳法则和求解一元高次方程的牛顿迭代法;
  音频播放器跳动的实时频谱背后是离散傅立叶变换算法;
  DOS时代的PCX图像文件格式使用的是简单有效的RLE压缩算法;
  RSA加密算法的光环之下是朴实的欧几里德算法、蒙哥马利算法和米勒-拉宾算法;
  井字棋、黑白棋、五子棋和俄罗斯方块游戏背后是各种有趣的AI算法;
  华容道游戏求解的简单穷举算法中还蕴藏着对棋盘状态的哈希算法;
  遗传算法神秘不可测,但用遗传算法求解0-1背包问题只用了60多行代码……
  《算法的乐趣》带你走进色彩缤纷的算法世界,让你尽享算法的乐趣。

作者简介

  王晓华 ,2005年毕业于华中科技大学,目前在中兴通讯上海研发中心从事光纤接入网通讯设备开发,担任EPON(以太网无源光网络)业务软件开发经理,参与开发的PON设备在全球部署过亿线,为数亿家庭提供宽带接入服务。
  业余时间喜欢研究算法和写作博客,乐趣就是用程序解决生活中的问题:
  为了方便使用Visual Studio 6.0开发软件,曾特意编写并开源了一个tabbar插件;
  为了文档安全,开发了一个基于layerFSD技术的透明文件加密系统;
  使用Source Insight软件觉得不习惯,于是以外挂的形式开发了TabSiPlus插件……

精彩书评

  ★“另外两本排名靠前的经典算法教材是Jon Kleinberg的Algorithm Design和Steven S Skiena的The Algorithm Design Manual。这两本出自名家之手的教材和很多教材一样,按照算法的类型或者背后的设计思路来组织内容。这是教材应该做的,“授人以鱼不如授人以渔”,传授思路而不是算法本身是教材的写作目的。可是算法有意思的地方首先在于算法本身,因为算法是为了解决实际问题而设计的,所以让大家认识到算法奥妙的自然顺序应该是先展示有趣的问题,再展示优雅的算法,结尾归纳设计思路。而这正是《算法的乐趣》吸引人的地方。
  “我曾经以为从乐趣出发阐述算法的书会从西方发芽,没想到先看到了一本中文书。这真超出了我的预料。”
  ——王益,LinkedIn高级主任分析师

  ★“这本书给我的惊喜是没有像一般的算法书一样单纯地去讲算法和数据结构本身,那样无论语言多风趣,只要一谈到关键的问题也会马上变得无趣起来。作者在每一章都举给出了一个实际的问题,然后尝试用算法去解决这个问题,没有局限于通用类算法,而是同时涵盖逻辑类算法、通用类算法和专业类算法,真正是在训练读者解决问题的能力,而解决问题的能力,正是任何一家公司所需人才的核心的技能。”
  ——黄鑫((飞林沙)),极光推送首席科学家

  ★“如果说《啊哈!算法》是算法界的小白书,内容太少看得不过瘾,那么这本《算法的乐趣》或许可以带你一起牛逼一起飞。当我刚拿到书的目录的时候,我就很期待,因为终于有一本算法书可以系统地和大伙说一说这些我也很想与大伙说的伟大算法。”
  ——啊哈磊,《啊哈!算法》作者

目录

第1章 程序员与算法
1.1 什么是算法
1.2 程序员必须要会算法吗
1.2.1 一个队列引发的惨案
1.2.2 我的第一个算法
1.3 算法的乐趣在哪里
1.4 算法与代码
1.5 总结
1.6 参考资料
第2章 算法设计的基础
2.1 程序的基本结构
2.1.1 顺序执行
2.1.2 循环结构
2.1.3 分支和跳转结构
2.2 算法实现与数据结构
2.2.1 基本数据结构在算法设计中的应用
2.2.2 复杂数据结构在算法设计中的应用
2.3 数据结构和数学模型与算法的关系
2.4 总结
2.5 参考资料
第3章 算法设计的常用思想
3.1 贪婪法
3.1.1 贪婪法的基本思想
3.1.2 贪婪法的例子:0-1 背包问题
3.2 分治法
3.2.1 分治法的基本思想
3.2.2 递归和分治,一对好朋友
3.2.3 分治法的例子:大整数Karatsuba 乘法算法
3.3 动态规划
3.3.1 动态规划的基本思想
3.3.2 动态规划法的例子:字符串的编辑距离
3.4 解空间的穷举搜索
3.4.1 解空间的定义
3.4.2 穷举解空间的策略
3.4.3 穷举搜索的例子:Google 方程式
3.5 总结
3.6 参考资料
第4章 阿拉伯数字与中文数字
4.1 中文数字的特点
4.1.1 中文数字的权位和小节
4.1.2 中文数字的零
4.2 阿拉伯数字转中文数字
4.2.1 一个转换示例
4.2.2 转换算法设计
4.2.3 算法实现
4.2.4 中文大写数字
4.3 中文数字转阿拉伯数字
4.3.1 转换的基本方法
4.3.2 算法实现
4.4 数字转换的测试用例
4.5 总结
4.6 参考资料
第5章 三个水桶等分8 升水的问题
5.1 问题与求解思路
5.2 建立数学模型
5.2.1 状态的数学模型与状态树
5.2.2 倒水动作的数学模型
5.3 搜索算法
5.3.1 状态树的遍历
5.3.2 剪枝和重复状态判断
5.4 算法实现
5.5 总结
5.6 参考资料
第6章 妖怪与和尚过河问题
6.1 问题与求解思路
6.2 建立数学模型
6.2.1 状态的数学模型与状态树
6.2.2 过河动作的数学模型
6.3 搜索算法
6.3.1 状态树的遍历
6.3.2 剪枝和重复状态判断
6.4 算法实现
6.5 总结
6.6 参考资料
第7章 稳定匹配与舞伴问题
7.1 稳定匹配问题
7.1.1 什么是稳定匹配
7.1.2 Gale-Shapley 算法原理
7.2 Gale-Shapley 算法的应用实例
7.2.1 算法实现
7.2.2 改进优化:空间换时间
7.3 有多少稳定匹配
7.3.1 穷举所有的完美匹配
7.3.2 不稳定因素的判断算法
7.3.3 穷举的结果
7.4 二部图与二分匹配
7.4.1 最大匹配与匈牙利算法
7.4.2 带权匹配与Kuhn-Munkres算法
7.5 总结
7.6 参考资料
第8章 爱因斯坦的思考题
8.1 问题的答案
8.2 分析问题的数学模型
8.2.1 基本模型定义
8.2.2 线索模型定义
8.3 算法设计
8.3.1 穷举所有的组合结果
8.3.2 利用线索判定结果的正确性
8.4 总结
8.5 参考资料
第9章 项目管理与图的拓扑排序
9.1 AOV 网和AOE 网
9.2 拓扑排序
9.2.1 拓扑排序的基本过程
9.2.2 按照活动开始时间排序
9.3 关键路径算法
9.3.1 什么是关键路径
9.3.2 计算关键路径的算法
9.4 总结
9.5 参考资料
第10章 RLE 压缩算法与PCX 图像文件格式
10.1 RLE 压缩算法
10.1.1 连续重复数据的处理
10.1.2 连续非重复数据的处理
10.1.3 算法实现
10.2 RLE 与PCX 图像文件格式
10.2.1 PCX 图像文件格式
10.2.2 PCX_RLE 算法
10.2.3 256 色PCX 文件的解码和显示
10.3 总结
10.4 参考资料
第11章 算法与历法
11.1 格里历(公历)生成算法
11.1.1 格里历的历法规则
11.1.2 今天星期几
11.1.3 生成日历的算法
11.1.4 日历变更那点事儿
11.2 二十四节气的天文学计算
11.2.1 二十四节气的起源
11.2.2 二十四节气的天文学定义
11.2.3 VSOP-82/87 行星理论
11.2.4 误差修正--章动
11.2.5 误差修正--光行差
11.2.6 用牛顿迭代法计算二十四节气
11.3 农历朔日(新月)的天文学计算
11.3.1 日月合朔的天文学定义
11.3.2 ELP-2000/82 月球理论
11.3.3 误差修正--地球轨道离心率修正
11.3.4 误差修正--黄经摄动
11.3.5 月球地心视黄经和最后的修正--地球章动
11.3.6 用牛顿迭代法计算日月合朔
11.4 农历的生成算法
11.4.1 中国农历的起源与历法规则
11.4.2 中国农历的推算
11.4.3 一个简单的"年历"
11.5 总结
11.6 参考资料
第12章 实验数据与曲线拟合
12.1 曲线拟合
12.1.1 曲线拟合的定义
12.1.2 简单线性数据拟合的例子
12.2 最小二乘法曲线拟合
12.2.1 最小二乘法原理
12.2.2 高斯消元法求解方程组
12.2.3 最小二乘法解决"速度与加速度"实验
12.3 三次样条曲线拟合
12.3.1 插值函数
12.3.2 样条函数的定义
12.3.3 边界条件
12.3.4 推导三次样条函数
12.3.5 追赶法求解方程组
12.3.6 三次样条曲线拟合算法实现
12.3.7 三次样条曲线拟合的效果
12.4 总结
12.5 参考资料
第13章 非线性方程与牛顿迭代法
13.1 非线性方程求解的常用方法
13.1.1 公式法
13.1.2 二分逼近法
13.2 牛顿迭代法的数学原理
13.3 用牛顿迭代法求解非线性方程的实例
13.3.1 导函数的求解与近似公式
13.3.2 算法实现
13.4 参考资料
第14章 计算几何与计算机图形学
14.1 计算几何的基本算法
14.1.1 点与矩形的关系
14.1.2 点与圆的关系
14.1.3 矢量的基础知识
14.1.4 点与直线的关系
14.1.5 直线与直线的关系
14.1.6 点与多边形的关系
14.2 直线生成算法
14.2.1 什么是光栅图形扫描转换
14.2.2 数值微分法
14.2.3 Bresenham 算法
14.2.4 对称直线生成算法
14.2.5 两步算法
14.2.6 其他直线生成算法
14.3 圆生成算法
14.3.1 圆的八分对称性
14.3.2 中点画圆法
14.3.3 改进的中点画圆法--Bresenham 算法
14.3.4 正负判定画圆法
14.4 椭圆生成算法
14.4.1 中点画椭圆法
14.4.2 Bresenham 椭圆算法
14.5 多边形区域填充算法
14.5.1 种子填充算法
14.5.2 扫描线填充算法
14.5.3 改进的扫描线填充算法
14.5.4 边界标志填充算法
14.6 总结
14.7 参考资料
第15章 音频频谱和均衡器与傅里叶变换算法
15.1 实时频谱显示的原理
15.2 离散傅里叶变换
15.2.1 什么是傅里叶变换
15.2.2 傅里叶变换原理
15.2.3 快速傅里叶变换算法的实现
15.3 傅里叶变换与音频播放的实时频谱显示
15.3.1 频域数值的特点分析
15.3.2 从音频数据到功率频谱
15.3.3 音频播放时实时频谱显示的例子
15.4 破解电话号码的小把戏
15.4.1 拨号音的频谱分析
15.4.2 根据频谱数据反推电话号码
15.5 离散傅里叶逆变换
15.5.1 快速傅里叶逆变换的推导
15.5.2 快速傅里叶逆变换的算法实现
15.6 利用傅里叶变换实现频域均衡器
15.6.1 频域均衡器的实现原理
15.6.2 频域信号的增益与衰减
15.6.3 均衡器的实现--仿Foobar的18 段均衡器
15.7 总结
15.8 参考资料
第16章 全局最优解与遗传算法
16.1 遗传算法的原理
16.1.1 遗传算法的基本概念
16.1.2 遗传算法的处理流程
16.2 遗传算法求解0-1 背包问题
16.2.1 基因编码和种群初始化
16.2.2 适应度函数
16.2.3 选择算子设计与轮盘赌算法
16.2.4 交叉算子设计
16.2.5 变异算子设计
16.2.6 这就是遗传算法
16.3 总结
16.4 参考资料
第17章 计算器程序与大整数计算
17.1 哦,溢出了,出洋相的计算器程序
17.2 大整数计算的原理
17.2.1 大整数加法
17.2.2 大整数减法
17.2.3 大整数乘法
17.2.4 大整数除法与模
17.2.5 大整数乘方运算
17.3 大整数类的使用
17.3.1 与Windows的计算器程序一决高下
17.3.2 最大公约数和最小公倍数
17.3.3 用扩展欧几里得算法求模的逆元
17.4 总结
17.5 参考资料
第18章 RSA 算法--加密与签名
18.1 RSA 算法的开胃菜
18.1.1 将模幂运算转化为模乘运算
18.1.2 模乘运算与蒙哥马利算法
18.1.3 模幂算法
18.1.4 素数检验与米勒-拉宾算法
18.2 RSA 算法原理
18.2.1 RSA 算法的数学理论
18.2.2 加密和解密算法
18.2.3 RSA 算法的安全性
18.3 数据块分组加密
18.3.1 字节流与大整数的转换
18.3.2 PCKS 与OAEP 加密填充模式
18.3.3 数据加密算法实现
18.3.4 数据解密算法实现
18.4 RSA 签名与身份验证
18.4.1 RSASSA-PKCS 与RSASSAPSS签名填充模式
18.4.2 签名算法实现
18.4.3 验证签名算法实现
18.5 总结
18.6 参考资料
第19章 数独游戏
19.1 数独游戏的规则与技巧
19.1.1 数独游戏的规则
19.1.2 数独游戏的常用技巧
19.2 计算机求解数独问题
19.2.1 建立问题的数学模型
19.2.2 算法实现
19.2.3 与传统穷举方法的结果对比
19.3 关于数独的趣味话题
19.3.1 数独游戏有多少终盘
19.3.2 史上最难的数独游戏
19.4 总结
19.5 参考资料
第20章 华容道游戏
20.1 华容道游戏介绍
20.2 自动求解的算法原理
20.2.1 定义棋盘的局面
20.2.2 算法思路
20.3 自动求解的算法实现
20.3.1 棋局状态与Zobrist 哈希算法
20.3.2 重复棋局和左右镜像的处理
20.3.3 正确结果的判断条件
20.3.4 武将棋子的移动
20.3.5 棋局的搜索算法
20.4 总结
20.5 参考资料
第21章 A*寻径算法
21.1 寻径算法演示程序
21.2 Dijkstra 算法
21.2.1 Dijkstra 算法原理
21.2.2 Dijkstra 算法实现
21.2.3 Dijkstra 算法演示程序
21.3 带启发的搜索算法--A*算法
21.3.1 A*算法原理
21.3.2 常用的距离评估函数
21.3.3 A*算法实现
21.4 总结
21.5 参考资料
第22章 俄罗斯方块游戏
22.1 俄罗斯方块游戏规则
22.2 俄罗斯方块游戏人工智能的算法原理
22.2.1 影响评价结果的因素
22.2.2 常用的俄罗斯方块游戏人工智能算法
22.2.3 Pierre Dellacherie 评估算法
22.3 Pierre Dellacherie 算法实现
22.3.1 基本数学模型和数据结构定义
22.3.2 算法实现
22.4 总结
22.5 参考资料
第23章 博弈树与棋类游戏
23.1 棋类游戏的AI
23.1.1 博弈与博弈树
23.1.2 极大极小值搜索算法
23.1.3 负极大极搜索算法
23.1.4 "α-β"剪枝算法
23.1.5 估值函数
23.1.6 置换表与哈希函数
23.1.7 开局库与终局库
23.2 井字棋--最简单的博弈游戏
23.2.1 棋盘与棋子的数学模型
23.2.2 估值函数与估值算法
23.2.3 如何产生走法(落子方法)
23.3 奥赛罗棋(黑白棋)
23.3.1 棋盘与棋子的数学模型
23.3.2 估值函数与估值算法
23.3.3 搜索算法实现
23.3.4 最终结果
23.4 五子棋
23.4.1 棋盘与棋子的数学模型
23.4.2 估值函数与估值算法
23.4.3 搜索算法实现
23.4.4 最终结果
23.5 总结
23.6 参考资料
附录A 算法设计的常用技巧
A.1 数组下标处理
A.2 一重循环实现两重循环的功能
A.3 棋盘(迷宫)类算法方向遍历
A.4 代码的一致性处理技巧
A.5 链表和数组的配合使用
A.6 "以空间换时间"的常用技巧
A.7 利用表驱动避免长长的switch-case
附录B 一个棋类游戏的设计框架
B.1 代码框架的整体结构
B.2 代码框架的使用方法

前言/序言

  程序员与算法,这是一个永恒的话题,无论在哪个论坛,只要出现此类主题的帖子,一定会看到两种针锋相对的观点的“激烈碰撞”。其实泡过论坛的人都知道,两种观点“激烈辩论”的惨烈程度往往可以上升到互相问候先人的高度,即使是技术论坛也不例外。在准备此书之前,我在博客的“算法系列”专栏已经陆陆续续地写了有一年多的时间,在此期间,不断有读者问我:“程序员必须会算法吗?”我实在不想让我的博客成为喷满各种口水的是非之地,所以一般不正面回答,只是笼统地说些“各行各业情况都不尽相同”之类的话,避免站队。
  程序员对算法通常怀有复杂的感情,算法很重要是大家的共识,但是是否每个程序员都必须学算法是主要的分歧点。本书是想重新定义程序员对算法的理解,并不想通过说教的方式给出到底是学还是不学的结论。很多人可能觉得像人工智能、视频与音频处理以及数据搜索与挖掘这样高大上的内容才能称为算法,往往觉得算法深不可测。但是这些其实都不是具体的算法,而是一系列算法的集合,这里面既有各种大名鼎鼎的算法,比如神经网络、遗传算法、离散傅里叶变换算法以及各种插值算法,也有不起眼的排序和概率计算的算法。你必须深入地了解它们,才会领略到算法的实质——解决问题。忽视这一点,片面地或抽象地理解算法,就会使对算法的理解变得形而上学。在我的博客里就有人留言质疑:“穷举也算是算法?”且不说搜索和枚举是算法的基础设计模式之一,单就那么多的NPC问题(比如著名的汉密尔顿回路问题,至今还没有找到多项式时间的算法),实际上,从只有穷举算法和其他随机搜索算法才能求解这一点看,任何人都不能小看它。
  狭隘的算法定义会将自己局限在一个小角落里,从而错过了整个色彩缤纷的算法世界。本书将带你开启一段算法之旅,在这里,你将会看到各种构造算法的基础方法,比如贪婪法、分治法、动态规划法,等等,也可以通过一个个示例看到如何应用这些算法来解决实际问题。通过对“爱因斯坦的思考题”“三个水桶等分水”“妖怪与和尚过河问题”等趣味智力题的计算机求解算法设计,你可以领会到算法设计的三个关键问题,以及对这些问题的处理方法,为以后解决这样的问题提供举一反三的基础。
  在生活中,凡是有乐趣的地方就有算法。本书将介绍生活中无处不在的算法。在历法计算的章节里,你会看到霍纳法则(Horner’srule)的使用和求解一元高次方程的牛顿迭代法;音频播放器上跳动的频谱,背后是离散傅里叶变换算法;DOS时代著名的PCX图像文件格式使用的RLE压缩算法是如此简单,但是却非常有效;RSA加密算法的光环之下是朴实的欧几里得算法、蒙哥马利算法和米勒?拉宾算法;华容道游戏求解的简单穷举算法中还蕴藏着对棋盘状态的哈希算法……遗传算法神秘不可测,但是用遗传算法求解0-1背包问题只用了60多行代码。事实上,抛开对遗传算法的深层次研究和在各种专业领域内的扩展应用,单就算法原理来说,它就是这么简单。深蓝战胜卡斯特罗之后,人类棋手在与计算机的博弈中就完全处于下风,人工智能真的这么神奇?人工智能确实是个神奇的领域,但就计算机下棋这件事来说,却并不怎么神奇,算法的基本原理简单得让人难以置信,看看第23章你就知道了。
  算法之大,大到可以囊括宇宙万物的运行规律,算法之小,小到寥寥数行代码即可展现一个神奇的功能。算法是琐碎的,以至于常常被人们忽视,然而忽视算法能力的培养所带来的代价是巨大的,第1章介绍的环形队列的例子就是一个最好的说明。我面试过很多求职者,我常常会让他们手写一个算法,我的题目是这样的:有一个由若干正整数组成的数列,数列中的每个数都不超过32,已知数列中存在重复的数字,请给出一个算法找出这个数列中所有重复出现的数。我期望求职者给我一个正确的算法实现,接下来我会问这个算法的时间复杂度是什么,有没有考虑过存在一个O(n)时间复杂度的算法。大部分求职者都知道自己的算法是O(n2)时间复杂度,但是都否认存在O(n)时间复杂度的算法。事实上这个题目是可以有O(n)时间复杂度的算法的,因为大家都忽略了一个重要的条件。这个题目并不难,但是仍有将近三分之一的面试者无法给出正确的算法,有的甚至还给我一张白纸。有人犯错误是正常现象,但是让我意外的是居然有三分之一的人写不出这个算法,算法设计的基本功被无视到这种地步是不正常的。
  程序员谈到算法言必称一些高大上的词汇,但是这些专有名词大部分人是用不到的,以至于人们常常认为算法不过如此,不会又如何?这种思想变得极端就会让人忽视算法的基础设计能力,这才是最要命的。在我们维护的网络设备上,用户的数据关系错综复杂,一个对线性表进行二重循环都想不到的人又怎么可能会维护这些数据?我希望程序员们提高基础的算法能力,先从培养兴趣开始或许是一个不错的切入点。
  本书挑选的算法例子,都围绕着“趣”字展开,都是简单且在生活中常见的算法,可能有些是你还没有意识到的。我上学的时候曾经做过一个MP3播放器程序,你可能觉得这主要就是利用一些音频解码算法吧?是的,这个是主要部分,但是一个功能完整的播放程序还用了很多你想不到的算法:为增加频谱显示和均衡器功能,使用了离散傅里叶变换算法;为计算频率功率谱,使用了加权平均值算法;为了匹配硬件输出设备与解码算法的性能差异,需要一个有多个缓冲区的队列管理音频数据块,这就引入了滑动窗口算法;为提供按照专辑名称或作者名称排序功能,使用了快速排序算法;为了平滑均衡器调节对音频的影响,使用了三次样条曲线插值算法;为了在两首歌曲之间切换时压制刺耳的杂音(通过填充一些舒适噪声的方式实现),还使用了正弦信号发生器算法。这些你都没有想到吧?其实还有更多的例子,比如大型项目管理软件中的工作节点排序功能和关键路径功能,背后支撑它们的却是简单的有向图拓扑排序算法。这是不是很有趣?生活中处处都是算法,程序员又怎么可能与算法绝缘?
  再次重申一点,本书没有任何关于算法重要性的说教,当你看到本书时,我希望你的表情是“啊哈,原来如此!”,或者是“嗯,有意思!”,并从中获得乐趣。本书几乎所有章节都有相关算法实现和功能演示的代码,读者可以到我的博客中下载,也可以到图灵社区本书主页下载使用。