趣学算法 pdf
内容简介
本书内容按照算法策略分为7章。
第1章从算法之美、简单小问题、趣味故事引入算法概念、时间复杂度、空间复杂度的概念和计算方法，以及算法设计的爆炸性增量问题，使读者体验算法的奥妙。
第2～7章介绍经典算法的设计策略、实战演练、算法分析及优化拓展，分别讲解贪心算法、分治算法、动态规划、回溯法、分支限界法、线性规划和网络流。每一种算法都有4～10个实例，共50个大型实例，包括经典的构造实例和实际应用实例，按照问题分析、算法设计、完美图解、伪代码详解、实战演练、算法解析及优化拓展的流程，讲解清楚且通俗易懂。附录介绍常见的数据结构及算法改进用到的相关知识，包括sort函数、优先队列、邻接表、并查集、四边不等式、排列树、贝尔曼规则、增广路复杂性计算等内容。
本书可作为程序员的学习用书，也适合从未有过编程经验但又对算法有强烈兴趣的初学者使用，同时也可作为高等院校计算机、数学及相关专业的师生用书和培训学校的教材。
作者简介
陈小玉，副教授，硕士，高级程序员，研究方向：智能计算、机器学习与数据挖掘。主讲《数据结构》、《算法设计与分析》、《人工智能》等专业课程，并发表过多篇计算机专业论文和项目。
目录
第1章 算法之美 1
1．1 打开算法之门 2
1．2 妙不可言—算法复杂性 2
1．3 美不胜收—魔鬼序列 9
1．4 灵魂之交—马克思手稿中的数学题 16
1．5 算法学习瓶颈 21
1．6 你怕什么 22
第2章 贪心算法 24
2．1 人之初，性本贪 25
2．1．1 贪心本质 25
2．1．2 贪亦有道 26
2．1．3 贪心算法秘籍 26
2．2 加勒比海盗船—最优装载问题 27
2．2．1 问题分析 27
2．2．2 算法设计 28
2．2．3 完美图解 28
2．2．4 伪代码详解 29
2．2．5 实战演练 30
2．2．6 算法解析及优化拓展 31
2．3 阿里巴巴与四十大盗—背包问题 32
2．3．1 问题分析 32
2．3．2 算法设计 33
2．3．3 完美图解 33
2．3．4 伪代码详解 34
2．3．5 实战演练 35
2．3．6 算法解析及优化拓展 36
2．4 高级钟点秘书—会议安排 37
2．4．1 问题分析 38
2．4．2 算法设计 39
2．4．3 完美图解 40
2．4．4 伪代码详解 41
2．4．5 实战演练 42
2．4．6 算法解析及优化拓展 45
2．5 一场说走就走的旅行—最短路径 45
2．5．1 问题分析 46
2．5．2 算法设计 46
2．5．3 完美图解 47
2．5．4 伪代码详解 51
2．5．5 实战演练 52
2．5．6 算法解析及优化拓展 55
2．6 神秘电报密码—哈夫曼编码 59
2．6．1 问题分析 60
2．6．2 算法设计 62
2．6．3 完美图解 63
2．6．4 伪代码详解 65
2．6．5 实战演练 74
2．6．6 算法解析及优化拓展 77
2．7 沟通无限校园网—最小生成树 77
2．7．1 问题分析 78
2．7．2 算法设计 79
2．7．3 完美图解 80
2．7．4 伪代码详解 87
2．7．5 实战演练 88
2．7．6 算法解析 90
2．7．7 算法优化拓展 90
第3章 分治法 99
3．1 山高皇帝远 100
3．1．1 治众如治寡—分而治之 100
3．1．2 天时地利人和—分治算法要素 100
3．1．3 分治算法秘籍 101
3．2 猜数游戏—二分搜索技术 101
3．2．1 问题分析 101
3．2．2 算法设计 102
3．2．3 完美图解 102
3．2．4 伪代码详解 103
3．2．5 实战演练 104
3．2．6 算法解析与拓展 105
3．3 合久必分，分久必合—合并排序 107
3．3．1 问题分析 108
3．3．2 算法设计 108
3．3．3 完美图解 108
3．3．4 伪代码详解 108
3．3．5 实战演练 111
3．3．6 算法解析与拓展 112
3．4 兵贵神速—快速排序 113
3．4．1 问题分析 114
3．4．2 算法设计 115
3．4．3 完美图解 116
3．4．4 伪代码详解 117
3．4．5 实战演练 118
3．4．6 算法解析与拓展 120
3．5 效率至上—大整数乘法 124
3．5．1 问题分析 124
3．5．2 算法设计 125
3．5．3 完美图解 126
3．5．4 伪代码详解 128
3．5．5 实战演练 132
3．5．6 算法解析与拓展 135
3．6 分治算法复杂度求解秘籍 137
第4章 动态规划 141
4．1 神奇的兔子序列 142
4．2 动态规划基础 143
4．2．1 算法思想 143
4．2．2 算法要素 143
4．2．3 解题秘籍 143
4．3 孩子有多像爸爸—最长的公共子序列 145
4．3．1 问题分析 145
4．3．2 算法设计 147
4．3．3 完美图解 148
4．3．4 伪代码详解 152
4．3．5 实战演练 153
4．3．6 算法解析及优化拓展 155
4．4 DNA基因鉴定—编辑距离 156
4．4．1 问题分析 156
4．4．2 算法设计 158
4．4．3 完美图解 159
4．4．4 伪代码详解 161
4．4．5 实战演练 162
4．4．6 算法解析及优化拓展 163
4．5 长江一日游—游艇租赁 164
4．5．1 问题分析 164
4．5．2 算法设计 166
4．5．3 完美图解 166
4．5．4 伪代码详解 170
4．5．5 实战演练 171
4．5．6 算法解析及优化拓展 172
4．6 快速计算—矩阵连乘 172
4．6．1 问题分析 173
4．6．2 算法设计 176
4．6．3 完美图解 176
4．6．4 伪代码详解 180
4．6．5 实战演练 181
4．6．6 算法解析及优化拓展 182
4．7 切呀切披萨—最优三角剖分 183
4．7．1 问题分析 183
4．7．2 算法设计 186
4．7．3 完美图解 187
4．7．4 伪代码详解 191
4．7．5 实战演练 192
4．7．6 算法解析及优化拓展 194
4．8 小石子游戏—石子合并 194
4．8．1 问题分析 195
4．8．2 算法设计 197
4．8．3 完美图解 198
4．8．4 伪代码详解 203
4．8．5 实战演练 205
4．8．6 算法解析及优化拓展 206
4．9 大卖场购物车1—0-1背包问题 209
4．9．1 问题分析 210
4．9．2 算法设计 211
4．9．3 完美图解 212
4．9．4 伪代码详解 216
4．9．5 实战演练 217
4．9．6 算法解析及优化拓展 218
4．10 快速定位—最优二叉搜索树 220
4．10．1 问题分析 221
4．10．2 算法设计 225
4．10．3 完美图解 226
4．10．4 伪代码详解 239
4．10．5 实战演练 241
4．10．6 算法解析及优化拓展 243
4．11 动态规划算法秘籍 246
第5章 回溯法 248
5．1 回溯法基础 249
5．1．1 算法思想 249
5．1．2 算法要素 249
5．1．3 解题秘籍 251
5．2 大卖场购物车2—0-1背包问题 252
5．2．1 问题分析 252
5．2．2 算法设计 253
5．2．3 完美图解 255
5．2．4 伪代码详解 258
5．2．5 实战演练 259
5．2．6 算法解析 262
5．2．7 算法优化拓展 262
5．3 部落护卫队—最大团 265
5．3．1 问题分析 266
5．3．2 算法设计 267
5．3．3 完美图解 269
5．3．4 伪代码详解 274
5．3．5 实战演练 275
5．3．6 算法解析及优化拓展 277
5．4 地图调色板—地图着色 278
5．4．1 问题分析 278
5．4．2 算法设计 279
5．4．3 完美图解 280
5．4．4 伪代码详解 285
5．4．5 实战演练 286
5．4．6 算法解析及优化拓展 288
5．5 一山不容二虎—n皇后问题 289
5．5．1 问题分析 290
5．5．2 算法设计 291
5．5．3 完美图解 292
5．5．4 伪代码详解 300
5．5．5 实战演练 301
5．5．6 算法解析及优化拓展 303
5．6 机器零件加工—最优加工顺序 305
5．6．1 问题分析 305
5．6．2 算法设计 308
5．6．3 完美图解 308
5．6．4 伪代码详解 313
5．6．5 实战演练 314
5．6．6 算法解析 316
5．6．7 算法优化拓展 316
5．7 奇妙之旅1—旅行商问题 319
5．7．1 问题分析 319
5．7．2 算法设计 320
5．7．3 完美图解 321
5．7．4 伪代码详解 330
5．7．5 实战演练 331
5．7．6 算法解析及优化拓展 333
5．8 回溯法算法秘籍 336
第6章 分支限界法 338
6．1 横行天下—广度优先 339
6．1．1 算法思想 340
6．1．2 算法步骤 340
6．1．3 解题秘籍 341
6．2 大卖场购物车3—0-1背包问题 341
6．2．1 问题分析 342
6．2．2 算法设计 343
6．2．3 完美图解 345
6．2．4 伪代码详解 350
6．2．5 实战演练 352
6．2．6 算法解析 355
6．2．7 算法优化拓展—优先队列式分支限界法 356
6．3 奇妙之旅2—旅行商问题 366
6．3．1 问题分析 366
6．3．2 算法设计 367
6．3．3 完美图解 368
6．3．4 伪代码详解 371
6．3．5 实战演练 373
6．3．6 算法解析 376
6．3．7 算法优化拓展 377
6．4 铺设电缆—最优工程布线 385
6．4．1 问题分析 386
6．4．2 算法设计 386
6．4．3 完美图解 387
6．4．4 伪代码详解 399
6．4．5 实战演练 400
6．4．6 算法解析及优化拓展 403
6．5 回溯法与分支限界法的异同 404
第7章 线性规划网络流 405
7．1 线性规划问题 406
7．1．1 线性规划标准型 408
7．1．2 单纯形算法图解 409
7．1．3 解题秘籍 413
7．1．4 练习 413
7．2 工厂最大效益—单纯形算法 414
7．2．1 问题分析 414
7．2．2 完美图解 415
7．2．3 伪代码详解 418
7．2．4 实战演练 420
7．2．5 算法解析及优化拓展 423
7．3 最大网络流—最短增广路算法 424
7．3．1 问题分析 424
7．3．2 增广路算法 427
7．3．3 完美图解 431
7．3．4 伪代码详解 437
7．3．5 实战演练 439
7．3．6 算法解析 441
7．3．7 算法优化拓展—重贴标签算法ISAP 442
7．4 最小费用最大流—最小费用路算法 455
7．4．1 问题分析 456
7．4．2 算法设计 456
7．4．3 完美图解 457
7．4．4 伪代码详解 459
7．4．5 实战演练 461
7．4．6 算法解析 465
7．4．7 算法优化拓展—消圈算法 466
7．5 精明的老板—配对方案问题 468
7．5．1 问题分析 468
7．5．2 算法设计 469
7．5．3 完美图解 469
7．5．4 伪代码详解 470
7．5．5 实战演练 471
7．5．6 算法解析 475
7．5．7 算法优化拓展—匈牙利算法 475
7．6 国际会议交流—圆桌问题 480
7．6．1 问题分析 481
7．6．2 算法设计 482
7．6．3 完美图解 482
7．6．4 伪代码详解 484
7．6．5 实战演练 485
7．6．6 算法解析及优化拓展 489
7．7 要考试啦—试题库问题 489
7．7．1 问题分析 490
7．7．2 算法设计 490
7．7．3 完美图解 491
7．7．4 伪代码详解 493
7．7．5 实战演练 494
7．7．6 算法解析及优化拓展 498
7．8 太空实验计划—最大收益问题 499
7．8．1 问题分析 499
7．8．2 算法设计 500
7．8．3 完美图解 502
7．8．4 伪代码详解 505
7．8．5 实战演练 506
7．8．6 算法解析及优化拓展 510
7．9 央视娱乐节目购物街—方格取数问题 511
7．9．1 问题分析 511
7．9．2 算法设计 512
7．9．3 完美图解 513
7．9．4 伪代码详解 514
7．9．5 实战演练 516
7．9．6 算法解析及优化拓展 520
7．10 走着走着，就走到了西藏—旅游路线问题 521
7．10．1 问题分析 521
7．10．2 算法设计 523
7．10．3 完美图解 523
7．10．4 伪代码详解 525
7．10．5 实战演练 528
7．10．6 算法解析及优化拓展 532
7．11 网络流问题解题秘籍 533
附录A 特征方程和通项公式 534
附录B sort函数 537
附录C 优先队列 541
附录D 邻接表 549
附录E 并查集 555
附录F 四边不等式 561
附录G 排列树 565
附录H 贝尔曼规则 579
附录I 增广路中称为关键边的次数 582
附录J 最大流最小割定理 585
感悟与笔记
1.1 基础编程模型
介绍了相关的语法、语言特性和库。本书使用Java编程语言编写的程序实现算法。我们把描述和实现算法所用到的语言特性、软件库和操作系统特性总称为基础编程模型。另一本入门书籍An Introduction to Programming in Java: An Interdisciplinary Approach也使用了这个模型。
1.1.1 Java程序的基本结构
一段Java程序（类）要么是一个静态方法（函数）库，要么定义了一个数据结构。要创建静态方法库和定义数据类型，会用到如下几种语法：原始数据类型、语句（声明、赋值、条件、循环、调用和返回）、数组、静态方法、字符串、标准输入/输出、数据抽象。
1.1.2 原始数据类型与表达式
int、double、boolean、char、long、short、byte、float。
1.1.3 语句
声明、赋值、条件、循环、break和continue。
1.1.4 简便记法
声明并初始化、隐式赋值、单语句代码段、for语句。
1.1.5 数组
创建、初始化、二维数组。
1.1.6 静态方法
static、递归。
1.1.7 API
自定义标准库。
1.1.8 字符串
String。
1.1.9 输入输出
标准输入输出、标准绘图库。
1.1.10 二分查找
以二分查找作为例子简单回顾。
1.1.11 展望
1.2 数据抽象
介绍了用Java实现抽象数据类型的过程，包括定义它的应用编程接口（API）然后通过Java的类机制来实现它以供各种用例使用——自定义类。
1.2.1 使用抽象数据类型
为了编写一个使用Counter（计数器）的简单数据类型的程序，需要写一份API，并重写toString()方法。导包，创建对象，使用对象，将对象返回。对象的数组。
1.2.2 抽象数据类型举例
介绍了很多Java内置的抽象数据类型：画图的、信息处理的、字符串、输入输出。
1.2.3 抽象数据类型的实现
介绍了类的相关知识，如构造函数、实例方法等。
1.2.4 更多抽象数据类型的实现
举例解释上一节：日期、累加器、可视化累加器。
1.2.5 数据类型的设计
封装、算法与抽象数据类型、接口、继承、字符串特点、等价性、内存管理、不可变形、异常、断言。
1.3 背包、队列和栈
用数组、变长数组和链表实现了背包、队列和栈的API，它们是全书算法实现的起点和样板。
1.3.1 API
无论做什么，先写API。每份API都含有一个无参数的构造函数、一个向集合中添加单个元素的方法、一个测试集合是否为空的方法和一个返回集合大小的方法。队列和栈都含有一个能够删除特定元素的方法。
泛型：我们定义一个集合，但不知道集合中储存数据的具体类型是什么，用 < T>表示。
自动装箱：int —> Integer
可迭代的集合类型：就是可以访问集合中的每一个元素的意思。
背包：一种元素之间没有相对顺序的集合，可以理解成一个背包中的弹球，每次迭代都是没有顺序的。我认为正是因为没有顺序，所以没有明确的办法区分出某一个元素，因此背包才不支持删除元素。
先进先出队列：好像没啥说的，就是队列呗。
下压栈：压栈弹栈，先进后出，基础概念。
算术表达式求值：用两个栈（一个用于保存运算符，一个用于保存操作数）实现表达式的运算。在不同的地方看过两次，真正用代码实现过一次，现在看来还跟陌生的东西一样。跟程序的机器级表示有神似之处。
会员免费下载
链接：https://pan.baidu.com/s/15FlKRWDM5qn9dw_8AKqXZg
提取码： ****** 查看
成为本站VIP会员即可无限下载。 请先点击百度网盘，看资源是否还在，不在请点击链接通知站长补资源。
资源标签点击标签可查看对应分类的资源
