算法的乐趣PDF电子书下载

第1章 程序员与算法 1

1.1 什么是算法 2

1.2 程序员必须要会算法吗 2

1.2.1 一个队列引发的惨案 3

1.2.2 我的第一个算法 5

1.3 算法的乐趣在哪里 7

1.4 算法与代码 8

1.5 总结 9

1.6 参考资料 9

第2章 算法设计的基础 10

2.1 程序的基本结构 10

2.1.1 顺序执行 10

2.1.2 循环结构 11

2.1.3 分支和跳转结构 13

2.2 算法实现与数据结构 16

2.2.1 基本数据结构在算法设计中的应用 16

2.2.2 复杂数据结构在算法设计中的应用 19

2.3 数据结构和数学模型与算法的关系 24

2.4 总结 25

2.5 参考资料 25

第3章 算法设计的常用思想 26

3.1 贪婪法 26

3.1.1 贪婪法的基本思想 27

3.1.2 贪婪法的例子：0-1背包问题 27

3.2 分治法 30

3.2.1 分治法的基本思想 30

3.2.2 递归和分治，一对好朋友 31

3.2.3 分治法的例子：大整数Karatsuba乘法算法 32

3.3 动态规划 34

3.3.1 动态规划的基本思想 34

3.3.2 动态规划法的例子：字符串的编辑距离 37

3.4 解空间的穷举搜索 40

3.4.1 解空间的定义 41

3.4.2 穷举解空间的策略 42

3.4.3 穷举搜索的例子：Google方程式 44

3.5 总结 46

3.6 参考资料 46

第4章 阿拉伯数字与中文数字 47

4.1 中文数字的特点 47

4.1.1 中文数字的权位和小节 48

4.1.2 中文数字的零 48

4.2 阿拉伯数字转中文数字 49

4.2.1 一个转换示例 49

4.2.2 转换算法设计 49

4.2.3 算法实现 50

4.2.4 中文大写数字 51

4.3 中文数字转阿拉伯数字 52

4.3.1 转换的基本方法 52

4.3.2 算法实现 52

4.4 数字转换的测试用例 54

4.5 总结 55

4.6 参考资料 55

第5章 三个水桶等分8升水的问题 56

5.1 问题与求解思路 57

5.2 建立数学模型 58

5.2.1 状态的数学模型与状态树 58

5.2.2 倒水动作的数学模型 59

5.3 搜索算法 60

5.3.1 状态树的遍历 60

5.3.2 剪枝和重复状态判断 61

5.4 算法实现 62

5.5 总结 64

5.6 参考资料 64

第6章 妖怪与和尚过河问题 65

6.1 问题与求解思路 66

6.2 建立数学模型 66

6.2.1 状态的数学模型与状态树 67

6.2.2 过河动作的数学模型 67

6.3 搜索算法 69

6.3.1 状态树的遍历 70

6.3.2 剪枝和重复状态判断 70

6.4 算法实现 71

6.5 总结 72

6.6 参考资料 73

第7章 稳定匹配与舞伴问题 74

7.1 稳定匹配问题 74

7.1.1 什么是稳定匹配 74

7.1.2 Gale-Shapley算法原理 75

7.2 Gale-Shapley算法的应用实例 77

7.2.1 算法实现 77

7.2.2 改进优化：空间换时间 80

7.3 有多少稳定匹配 81

7.3.1 穷举所有的完美匹配 81

7.3.2 不稳定因素的判断算法 82

7.3.3 穷举的结果 84

7.4 二部图与二分匹配 84

7.4.1 最大匹配与匈牙利算法 85

7.4.2 带权匹配与Kuhn-Munkres算法 88

7.5 总结 93

7.6 参考资料 94

第8章 爱因斯坦的思考题 95

8.1 问题的答案 96

8.2 分析问题的数学模型 96

8.2.1 基本模型定义 96

8.2.2 线索模型定义 98

8.3 算法设计 99

8.3.1 穷举所有的组合结果 99

8.3.2 利用线索判定结果的正确性 101

8.4 总结 103

8.5 参考资料 104

第9章 项目管理与图的拓扑排序 105

9.1 AOV网和AOE网 107

9.2 拓扑排序 108

9.2.1 拓扑排序的基本过程 108

9.2.2 按照活动开始时间排序 108

9.3 关键路径算法 111

9.3.1 什么是关键路径 112

9.3.2 计算关键路径的算法 113

9.4 总结 116

9.5 参考资料 116

第10章 RLE压缩算法与PCX图像文件格式 117

10.1 RLE压缩算法 117

10.1.1 连续重复数据的处理 117

10.1.2 连续非重复数据的处理 118

10.1.3 算法实现 118

10.2 RLE与PCX图像文件格式 121

10.2.1 PCX图像文件格式 121

10.2.2 PCX RLE算法 122

10.2.3 256色PCX文件的解码和显示 123

10.3 总结 124

10.4 参考资料 125

第11章 算法与历法 126

11.1 格里历（公历）生成算法 126

11.1.1 格里历的历法规则 126

11.1.2 今天星期几 127

11.1.3 生成日历的算法 131

11.1.4 日历变更那点事儿 132

11.2 二十四节气的天文学计算 134

11.2.1 二十四节气的起源 134

11.2.2 二十四节气的天文学定义 135

11.2.3 VSOP-82/87行星理论 137

11.2.4 误差修正——章动 141

11.2.5 误差修正——光行差 143

11.2.6 用牛顿迭代法计算二十四节气 144

11.3 农历朔日（新月）的天文学计算 146

11.3.1 日月合朔的天文学定义 147

11.3.2 ELP-2000/82月球理论 147

11.3.3 误差修正——地球轨道离心率修正 149

11.3.4 误差修正——黄经摄动 149

11.3.5 月球地心视黄经和最后的修正——地球章动 150

11.3.6 用牛顿迭代法计算日月合朔 151

11.4 农历的生成算法 152

11.4.1 中国农历的起源与历法规则 153

11.4.2 中国农历的推算 157

11.4.3 一个简单的“年历” 165

11.5 总结 166

11.6 参考资料 167

第12章 实验数据与曲线拟合 168

12.1 曲线拟合 168

12.1.1 曲线拟合的定义 168

12.1.2 简单线性数据拟合的例子 168

12.2 最小二乘法曲线拟合 169

12.2.1 最小二乘法原理 170

12.2.2 高斯消元法求解方程组 171

12.2.3 最小二乘法解决“速度与加速度”实验 172

12.3 三次样条曲线拟合 173

12.3.1 插值函数 174

12.3.2 样条函数的定义 174

12.3.3 边界条件 175

12.3.4 推导三次样条函数 176

12.3.5 追赶法求解方程组 179

12.3.6 三次样条曲线拟合算法实现 181

12.3.7 三次样条曲线拟合的效果 183

12.4 总结 184

12.5 参考资料 184

第13章 非线性方程与牛顿迭代法 185

13.1 非线性方程求解的常用方法 185

13.1.1 公式法 185

13.1.2 二分逼近法 186

13.2 牛顿迭代法的数学原理 187

13.3 用牛顿迭代法求解非线性方程的实例 188

13.3.1 导函数的求解与近似公式 188

13.3.2 算法实现 188

13.4 参考资料 189

第14章 计算几何与计算机图形学 190

14.1 计算几何的基本算法 190

14.1.1 点与矩形的关系 190

14.1.2 点与圆的关系 191

14.1.3 矢量的基础知识 191

14.1.4 点与直线的关系 194

14.1.5 直线与直线的关系 194

14.1.6 点与多边形的关系 196

14.2 直线生成算法 199

14.2.1 什么是光栅图形扫描转换 200

14.2.2 数值微分法 200

14.2.3 Bresenham算法 202

14.2.4 对称直线生成算法 204

14.2.5 两步算法 205

14.2.6 其他直线生成算法 207

14.3 圆生成算法 207

14.3.1 圆的八分对称性 208

14.3.2 中点画圆法 209

14.3.3 改进的中点画圆法——Bresenham算法 210

14.3.4 正负判定画圆法 211

14.4 椭圆生成算法 212

14.4.1 中点画椭圆法 213

14.4.2 Bresenham椭圆算法 215

14.5 多边形区域填充算法 217

14.5.1 种子填充算法 218

14.5.2 扫描线填充算法 223

14.5.3 改进的扫描线填充算法 229

14.5.4 边界标志填充算法 233

14.6 总结 236

14.7 参考资料 236

第15章 音频频谱和均衡器与傅里叶变换算法 237

15.1 实时频谱显示的原理 237

15.2 离散傅里叶变换 238

15.2.1 什么是傅里叶变换 239

15.2.2 傅里叶变换原理 239

15.2.3 快速傅里叶变换算法的实现 243

15.3 傅里叶变换与音频播放的实时频谱显示 245

15.3.1 频域数值的特点分析 245

15.3.2 从音频数据到功率频谱 246

15.3.3 音频播放时实时频谱显示的例子 248

15.4 破解电话号码的小把戏 251

15.4.1 拨号音的频谱分析 251

15.4.2 根据频谱数据反推电话号码 252

15.5 离散傅里叶逆变换 253

15.5.1 快速傅里叶逆变换的推导 254

15.5.2 快速傅里叶逆变换的算法实现 254

15.6 利用傅里叶变换实现频域均衡器 255

15.6.1 频域均衡器的实现原理 255

15.6.2 频域信号的增益与衰减 256

15.6.3 均衡器的实现——仿Foobar的18段均衡器 258

15.7 总结 259

15.8 参考资料 259

第16章 全局最优解与遗传算法 260

16.1 遗传算法的原理 260

16.1.1 遗传算法的基本概念 261

16.1.2 遗传算法的处理流程 262

16.2 遗传算法求解0-1背包问题 267

16.2.1 基因编码和种群初始化 267

16.2.2 适应度函数 268

16.2.3 选择算子设计与轮盘赌算法 268

16.2.4 交叉算子设计 270

16.2.5 变异算子设计 271

16.2.6 这就是遗传算法 272

16.3 总结 272

16.4 参考资料 273

第17章 计算器程序与大整数计算 274

17.1 哦，溢出了，出洋相的计算器程序 274

17.2 大整数计算的原理 275

17.2.1 大整数加法 276

17.2.2 大整数减法 278

17.2.3 大整数乘法 279

17.2.4 大整数除法与模 281

17.2.5 大整数乘方运算 282

17.3 大整数类的使用 283

17.3.1 与Windows的计算器程序一决高下 283

17.3.2 最大公约数和最小公倍数 284

17.3.3 用扩展欧几里得算法求模的逆元 286

17.4 总结 288

17.5 参考资料 288

第18章 RSA算法——加密与签名 289

18.1 RSA算法的开胃菜 289

18.1.1 将模幂运算转化为模乘运算 290

18.1.2 模乘运算与蒙哥马利算法 291

18.1.3 模幂算法 292

18.1.4 素数检验与米勒—拉宾算法 292

18.2 RSA算法原理 295

18.2.1 RSA算法的数学理论 295

18.2.2 加密和解密算法 296

18.2.3 RSA算法的安全性 297

18.3 数据块分组加密 297

18.3.1 字节流与大整数的转换 298

18.3.2 PCKS与OAEP加密填充模式 298

18.3.3 数据加密算法实现 300

18.3.4 数据解密算法实现 301

18.4 RSA签名与身份验证 302

18.4.1 RSASSA-PKCS与RSASSA-PSS签名填充模式 302

18.4.2 签名算法实现 304

18.4.3 验证签名算法实现 305

18.5 总结 305

18.6 参考资料 306

第19章 数独游戏 307

19.1 数独游戏的规则与技巧 307

19.1.1 数独游戏的规则 307

19.1.2 数独游戏的常用技巧 308

19.2 计算机求解数独问题 308

19.2.1 建立问题的数学模型 310

19.2.2 算法实现 311

19.2.3 与传统穷举方法的结果对比 312

19.3 关于数独的趣味话题 312

19.3.1 数独游戏有多少终盘 313

19.3.2 史上最难的数独游戏 314

19.4 总结 314

19.5 参考资料 315

第20章 华容道游戏 316

20.1 华容道游戏介绍 316

20.2 自动求解的算法原理 317

20.2.1 定义棋盘的局面 317

20.2.2 算法思路 319

20.3 自动求解的算法实现 320

20.3.1 棋局状态与Zobrist哈希算法 321

20.3.2 重复棋局和左右镜像的处理 323

20.3.3 正确结果的判断条件 325

20.3.4 武将棋子的移动 325

20.3.5 棋局的搜索算法 328

20.4 总结 329

20.5 参考资料 329

第21章 A＊寻径算法 330

21.1 寻径算法演示程序 330

21.2 Dijkstra算法 331

21.2.1 Dijkstra算法原理 332

21.2.2 Dijkstra算法实现 332

21.2.3 Dijkstra算法演示程序 333

21.3 带启发的搜索算法——A＊算法 335

21.3.1 A＊算法原理 336

21.3.2 常用的距离评估函数 337

21.3.3 A＊算法实现 340

21.4 总结 342

21.5 参考资料 342

第22章 俄罗斯方块游戏 343

22.1 俄罗斯方块游戏规则 343

22.2 俄罗斯方块游戏人工智能的算法原理 344

22.2.1 影响评价结果的因素 345

22.2.2 常用的俄罗斯方块游戏人工智能算法 346

22.2.3 Pierre Dellacherie评估算法 347

22.3 Pierre Dellacherie算法实现 349

22.3.1 基本数学模型和数据结构定义 350

22.3.2 算法实现 352

22.4 总结 358

22.5 参考资料 358

第23章 博弈树与棋类游戏 359

23.1 棋类游戏的AI 359

23.1.1 博弈与博弈树 360

23.1.2 极大极小值搜索算法 361

23.1.3 负极大极搜索算法 362

23.1.4 “α-β”剪枝算法 363

23.1.5 估值函数 365

23.1.6 置换表与哈希函数 366

23.1.7 开局库与终局库 368

23.2 井字棋——最简单的博弈游戏 368

23.2.1 棋盘与棋子的数学模型 369

23.2.2 估值函数与估值算法 370

23.2.3 如何产生走法（落子方法） 371

23.3 奥赛罗棋（黑白棋） 373

23.3.1 棋盘与棋子的数学模型 374

23.3.2 估值函数与估值算法 377

23.3.3 搜索算法实现 380

23.3.4 最终结果 384

23.4 五子棋 385

23.4.1 棋盘与棋子的数学模型 386

23.4.2 估值函数与估值算法 388

23.4.3 搜索算法实现 391

23.4.4 最终结果 393

23.5 总结 393

23.6 参考资料 393

附录A 算法设计的常用技巧 395

A.1 数组下标处理 395

A.2 一重循环实现两重循环的功能 396

A.3 棋盘（迷宫）类算法方向遍历 396

A.4 代码的一致性处理技巧 397

A.5 链表和数组的配合使用 398

A.6 “以空间换时间”的常用技巧 399

A.7 利用表驱动避免长长的switch-case 400

附录B 一个棋类游戏的设计框架 401

B.1 代码框架的整体结构 401

B.2 代码框架的使用方法 403