第一部分在线视频

那么为了让大家理解

ARM这个方法我们举一个小的例子

就是河内塔

河内塔中文变成汉诺塔

那么hahoi tower

我以前都叫做河内塔不知道跟河内有没有关系

这个问题是什么我们写成hnabc

这个H的就是hahoir的第一个字母

这个N呢是一个正整数

表示有n个盘子

这个abc是三根柱子

这个n个盘子的中间都有个洞

不是盛菜的盘子是中间有个洞的盘子

这n个盘子的大小都不一样

从小到大是一套n个盘子呢

一开始初始状态是全部套在a柱子上

指大的在下小的在上

就是我们这个图所表示的这是花了四个

就是大盘子在下小盘子在上

一个一个的套在a柱子上

这个问题是什么呢

让你把这个n个盘子移动到c柱子上

你说我给他搬过去不就得了嘛不行

要求是一次只能拿一个盘子

这个盘子不套在柱子上你不能拿第二个盘子

所以手里面只能拿着一个盘子

把这个盘子放下去以后你才能拿第二个盘子

那么这个盘子呢要求把n个盘子从小到大套在

C柱子上这个b柱子上是干什么的是作为一个缓冲区

你可以临时把这个盘子在b柱子上放一放

这样你就可以去拿下面一个盘子

所以hnabc就是n个盘子

原来在a柱子上用b柱子作为缓冲

一个一次移动到c柱子上

保持在任何状态底下

都是小盘子在上大盘在下

怎么移

我们这个目的很清楚了

就是要把这盘子移过去

所以数学家就说了

这还不好办吗

递归嘛

所以就写出来了一个递归公式

就是nhnabc等于什么呢

先把n减一个盘子

通过c柱子作为

缓冲把它都搬到b柱子上

然后a柱子上不就只剩下一个盘子了吗

你把这个最大的盘子搬到c柱子上

最下面

然后你在

把b柱子的n减一个盘子

用这个a柱子作为中介

把它移到c柱子上就完了

这就是一个递归公式

所以前面是n减一个盘子从a到b

中间那就是移动一个盘子从a到c

后面的是n减一个盘子从b到c

这个写成数学公式很漂亮也很清楚

但是我们的目的究竟是什么是递归公式吗

我们的目的

作为计算机的学生来讲这个例子

当然我们是要写成一个程序

要这个序列算出来

我现在先问问大家

这个盘子是不是必须要顺序的搬呢

显然是必须顺序的为什么呢

因为一次只能挪一个

你不可能并行的时候搬两个对不对

所以实际上操作的时候

实际上搬的时候

它是一个顺序的动作就像这个表达式

这个递归公式书写这样

是要有顺序来完成

但是我们想想我们写一个程序

只是要计算它的操作序列

并不是要真正的就搬这个盘子

因此我就没有必要顺序了我只要有本事

你告诉我第几步我就给你写出来

可以并行的计算对不对

你说我要知道第五步是怎么挪

他说我要知道第18步是怎么挪我如果有这个本事

我可以把这两个同时

告诉你我有两台计算机我可以同时都告诉你

所以这个目的我们如果通过分析清楚

不是要写出那个顺序序列

而是要计算每一步他怎么挪

因为我们只是计算并不是操作因此就有可能

并行的来进行计算

而且是最后我们的结果就是

可以并行的叫什么呢一踏糊涂

就是有多少步我如果有那么多机器

我可以一次把所有的步骤写出来

没有串行一次写完只要我的计算机够

我们怎么达到这个有了这个目的以后

我们再做往下研究

这样我们就不受这个递归公式的约束了

我们都知道递归公式给出来的程序

那个复杂性是很大的

那个计算量是很大的而且他要求的存储

也是很大的因为你都把前面算的都要存在那里

所以这个我们要避免这个我们不是

仅仅走到数学家给出这个公式就够了

我们的目的是要写出

某一步你给我任何一步我要写出他的

怎么移动从哪个柱子移到哪个柱子

所以递归效率低的程序

不是我们的目的我们要能够计算任意一步

他到底是怎么搬的

所以就这也写的很清楚我们新目的是直接写

出操作系列里面任意一步

好我们用xyz

来写一个操作步搬一个盘子所以我们不用写一了

就是从a柱子上

把盘子搬到z柱子上y我们只是写在那里

因为搬一个盘都不需要缓冲

但是我们把y留在那只是闲着的一个柱子

比方说一个盘子他的那个

操作是什么呢就是abc

x等于a

y等于b

z等于c

就是abc就这一个操作盘子就搬过去了

那么如果是两个盘子呢

我们就画成这个二叉树的形式

先左子数然后跟然后右子数

左字数是什么呢acb

就是先把a柱子上第一个盘子放到

B柱子然后把根根就是abc把这个根

A盘a柱子的最大的那个盘子搬到c柱子上

然后第三步把b柱上的那个盘子

因为一共就两个吗把它搬到c柱子上

所以二叉树呢我们把它表达成二叉树的形式

按照这样的方式就很有这个启发性

因为你看这个就是四个盘子这个不看最后一行的

就是四个盘子就写成一个二叉树就是这个样子

这是一个操作二叉树

就是操作起来先左再跟再右

咱们看第四层先acb

然后是跟abc

然后是右是bac

然后又是跟就是第二层的acb

然后是右边这个子树右边这个子树

先左是第四层的cba然后是根是cab

然后等等所以这样一来这个操作就写出来

这其实就是那个递归公式

我们给它用二叉树的形式表达出来

这样表达出来以后有什么好处

我们看n个盘子呢一共就有n层

n个盘子一共有n次

每一层的第一个移动第一个操作

如果是基数层的话一层三层的基数层

他一定是abc

如果它是偶数层的它一定是acb对不对

这就是它的规律

我们有了这个二叉树以后

我们也能找到规律了

这个就是有了目的指导下我们给出的

数学模型看你变成这样

一个二叉树

而不再是一个递归公式一个顺序的公式

这个二叉树我们看到操作上它的特点是

第一基数层的第一个操作一定是abc

偶数层的第一个操作一定是acb

另外同一层一定是旋转

第一个操作是abc第二个操作一定是把b

调到最前面来变成bac

然后第三个是把这个c调到前面变成cba

然后第四个又变成abc

总之在同一层他是

从第一个操作然后经过一次旋转第二个

得到第二操作

经过两次旋转得了第三个操作然后

就是这个第一个操作然后再选择一次

下一个再旋转一次下一个

在旋转一次又是下一个

所以在同一层它的规律

就是从第一个开始

我们知道第一个不是abc就是acb

然后旋转旋转旋转旋转就得出来

这是n个盘子四个盘子是这样n个盘子也是这样

这是它的规律性数学系统的规律性

我们再看看这同一棵树

他的具体步骤这个操作呢

这是操作部署把这个二叉树操作部署我们这

给出的是四个盘子

你看最底下一层咱们从左到跟到右

我们写出来的步数就是这样的

最下面一层的操作步数一定是第一步

第三步第五步第七步第九步第十一步

那么一共有多少步呢四个盘子一共有2的四次方

减一那么多步

N个盘子那就是二的n次方减一那么多步

那么2的四次方是16-1是15

所以底下一层的是从第一步

基数步到第15步

那么倒数第二层

是第二步

然后第六步第十步第十四步

什么意思就是二乘以一

2×3 2×5 2×7

所以呢倒数第二层是2的1次方

乘以13579

然后在上面一层呢就是2的2次方

然后是13579我们这个四个盘子那就是

2的2次方是4那第一个

就是4的1次方乘1加4的1次方

然后第二个乘以2的2次方乘三

就是12

那么顶层那就是2的3次方就是2的n次方减1

这就是它的规律

有了这个规律以后我们就可以写了

好我们知道这个操作是通过旋转

首先找到它在哪一层然后找到它是哪一个

然后旋转就能得到所以现在假定

这个写着呢就是这个二叉树

二叉操作数二叉步数

他的这个特征这个我刚才已经说过了

那么现在我们假定

你要计算第L步

这个L步因为我们知道一共有2的n次方减1

那么多个步属于这个L

一定是大于等于一小于等于2的n次方减1

你给了这一个数以后我把这个数L呢

分解成二的K次方

乘以一个m这个m是一个奇数

如果他是二的K次方那么我就知道

这个操作一定在第几层呢

第n减K层

因为最底下的一层是第n层

R的开次方他一定是

第n减k层

这个m基数呢就是它在这一层的第几个

第几个我们知道就经过旋转就可以了

对吧如果是第一个

你不需要旋转第二个

旋转一次第三个旋转两次第四个

不旋转就是第一个操作一样的等等