图解算法 - (EPUB全文下载)

文件大小：0.24 mb。
文件格式：epub 格式。
书籍内容：

图解算法
第1章 一切从观察开始
1.1 什么是算法
1.2 汉诺塔问题
1.3 汉诺塔问题的非递归算法
1.4 发现算法的技巧
学习效果评测
第2章 分而治之法
2.1 何谓分而治之法
2.2 找出最大值
2.3 时间复杂度
2.4 二维极点问题
2.5 快速排序法
2.6 快速排序法的时间复杂度
2.7 寻找第k小值问题
2.8 分而治之法的技巧
学习效果评测
第3章 动态规划
3.1 何谓动态规划
3.2 换零钱
3.3 数字金字塔
3.4 最长相同子字符串
3.5 安排公司聚会
3.6 动态规划的技巧
学习效果评测
第4章 贪婪法
4.1 何谓贪婪法
4.2 最小成本生成树
4.3 霍夫曼编码树
4.4 贪婪法的陷阱：0-1背包问题
4.5 单位时间工作调度问题
4.6 证明贪婪法并介绍Matroid理论
4.7 贪婪法的技巧
学习效果评测
第5章 修剪与搜索法
5.1 何谓修剪与搜索法
5.2 找坏蛋问题
5.3 猜数字问题
5.4 约瑟夫问题
5.5 简化的线性规划问题
5.6 修剪与搜索法的技巧
学习效果评测
第6章 树搜索法
6.1 何谓树搜索法
6.2 树状解空间：n个皇后问题
6.3 回溯法：涂色问题
6.4 广度优先搜索法：八数字谜题
6.5 加速技巧：旅行商问题
6.6 树搜索法的技巧
学习效果评测
第7章 问题转换
7.1 何谓问题转换
7.2 将相异代表系问题转换成二分图上的匹配问题
7.3 将二分图上的匹配问题转换成网络流图问题
7.4 将网络流图问题转换成线性规划问题
7.5 问题转换的技巧
学习效果评测
第8章 图算法
8.1 什么是图
8.2 连通分支
8.3 Dijkstra最短路径算法
8.4 Bellman-Ford最短路径算法
8.5 双连通分支
8.6 图算法的技巧
学习效果评测
第9章 计算几何
9.1 何谓计算几何
9.2 多边形中的点
9.3 天空轮廓
9.4 凸包
9.5 最近点对
9.6 计算几何的技巧
学习效果评测
第10章 算法的难题
10.1 什么是NP-Complete
10.2 集合P和集合NP
10.3 满足性问题
10.4 多项式时间转换
10.5 NP中的难题
10.6 NP-Complete的性质
10.7 NP-Complete的证明技巧
学习效果评测
第11章 逼近算法
11.1 什么是逼近算法
11.2 最小顶点覆盖问题
11.3 装箱问题
11.4 平面上的旅行商问题
11.5 逼近算法的技巧
学习效果评测
第12章 随机算法
12.1 什么是随机算法
12.2 随机快速排序法
12.3 质数测试
12.4 最小割算法
12.5 随机算法技巧
学习效果评测
参考文献
第1章　一切从观察开始
章节大纲
1.1　什么是算法
1.2　汉诺塔问题
1.3　汉诺塔问题的非递归算法
1.4　发现算法的技巧
折纸飞机的过程隐含一个算法
1.1　什么是算法
什么是算法（algorithms）？
简而言之，算法是在符合问题的限制下，将输入（input）转换成输出（output）的过程。
计算机算法是人类利用计算机解决问题的技巧之一。其实每个人都会一些算法。例如，厨师会将食材转换成美食；演奏家会将乐谱转换成迷人的音乐；小朋友将废纸折成纸飞机的过程也隐含一种算法。程序员（programmer）就是使用计算机执行某一种算法，以解决特定问题的人，如表1.1所示。
表1.1　算法存在于各行业中
如何设计算法？
设计算法的第一个好习惯就是观察。我们认为观察是一切发现的开始。本书开篇利用一个例子——汉诺塔（Hanoi Tower）问题说明观察和设计算法的关系。
1.2　汉诺塔问题
汉诺塔问题是一个古老的游戏。游戏的目的是将左方柱子上的盘子搬到右方的柱子。游戏的规则有三条：
（1）一次搬一只盘子。
（2）每根柱子只有最上面的盘子可被搬动。
（3）大盘子不可置于小盘子的上方。
图1.1所示为三只盘子汉诺塔问题的一个解法。
图1.1　所示为三只盘子汉诺塔问题的一个解法。
从上图得知，三只盘子的汉诺塔问题共需要7个步骤完成。很自然地，我们提出第一个问题：
n只盘子的汉诺塔问题，共需要几个步骤完成？
若这个问题无法立刻回答，则可先观察一些范例。
观察一些小例子，并记录其移动的次数。
为记录方便，我们使用数学符号Tn代表n只盘子汉诺塔问题所需要的搬运次数。尝试算出n小于9之前的Tn，如表1.2所示。
表1.2　观察汉诺塔问题的搬运次数
这个数列有什么规则？T9=？
Tn好像是很靠近2的几次方，Tn是2n-1吗？
如何证明Tn是2n-1？
不知道。
还有其他规则吗？
比较前后项的关系，好像后项是前项的两倍？不，是两倍加1。
可以使用符号将此关系写下来吗？
可以，Tn=2Tn-1+1。
为何前后项有这样的关系？
不知道。
如果Tn=2Tn-1+1是正确的，有助于证明Tn=2n-1吗？最常用的证明方法是什么？
也许可以利用数学归纳法（mathematical induction）证明Tn=2n-1。
证明过程如表1.3所示。
表1.3　利用数学归纳法证明Tn=2n-1
另一个简单的证明如表1.4所示。
表1.4　Tn=2n-1的另一个证明
我们只利用简单的观察便猜中了Tn=2n-1这个性质。虽然不知道为什么Tn=2Tn-1+1，但此性质有助于证明Tn=2n-1。接下来的一个问题是：
给出一个有n只盘子的汉诺塔问题，如何（找出）搬动盘子（的算法）？
若这个问题无法立刻回答，则可先尝试找出一个小例子的解答，并观察这个解答的规则。
以下为有4只盘子的汉诺塔问题的一个解答。根据先前发现的性质，我们得知共需要搬动24-1=15次，如图1.2所示。
搬动的过程中有什么规则呢？
好像有些成堆的盘子打散之后又成堆了。
可以解释其中的道理吗？
大概是为了搬动最底部且最大的盘子，必须先将上面的3只盘子全部搬到中间的柱子。
哪个步骤可以看出此特性？
步骤7。
图1.2　有4只盘子的汉诺塔问题的搬动 ............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。