如何理解汉诺塔的递归?

更多精彩尽在这里,详情点击:http://peacocklime.com/,迪奥戈-若塔

如果你有耐心翻到这里看到这个回答,相信大部分前面的回答并没有让你完全明白汉诺塔的递归算法应该怎么理解,那么我希望这个答案会是你浏览的最后一个。ps:篇幅稍微有点长,请耐心阅读,相信我,会有价值的。(毕竟是个人理解,若其中有不正确的地方望大家多多指正哈)

要用程序来解决这个问题,我们先定义一个移动函数:move(移动数,开始柱,中转柱,目标柱),例如 move(2,A,B,C) 表示将2个盘子从A柱(开始柱)借助B柱(中转柱)移动到C柱(目标柱)。

关于开始柱,中转柱,目标柱这三个概念可以用移动过程中的某个状态来理解,看下面一张图应该就能明白:

以上图的三层汉诺塔为例,开始柱指的是开始状态时存放所有盘子的柱子,中转柱指的是中间状态时暂时存放n-1个(三层就是3-1个)盘子的柱子,目标柱指的是盘子最终要移动到的柱子。这里需要注意,开始柱,中转柱,迪奥戈-若塔目标柱并不是一成不变的,而是会根据层次的不同而改变。(如果这里暂时不能理解的话,先读下去,再回头你就能明白了)。

当盘子只有一个的时候,只要直接将盘子从开始柱移动到目标柱就可以了,迪奥戈-若塔并没有中间状态(即不用借助中转柱),在move方法中可以用一句话表示该移动动作 print(A—C);

我想对于以上两个情况大家应该是没有什么疑问的,是可以确定的。然后我们来看三层的情况:

step1. 把除了最大的盘子之外的盘子从A移到B(注意对于这个步骤来说此时A为开始柱,C为中转柱,B为目标柱,这样才能完成把最上面的2个盘子从A—B的任务)

step2. 把最大的盘子从A移到C(对于这个步骤来说此时A为开始柱,B为中转柱,C为目标柱,这样才能把最大的盘子从A—C)

step3. 把除了最大的盘子之外的盘子从B移到C(注意对于这个步骤来说此时B为开始柱,A为中转柱,C为目标柱,这样才能完成把处于step2中的中转柱的2个盘子从B—C的任务)

情况三的描述可能一下子不是那么好理解,但是大家应该能发现情况三的step1和step3的形式和整整个情况二的形式很像吧?而且要注意到分析的层次不相同时,开始柱,中转柱,目标柱是不一样的。对于step1来说中转柱是C,对于step3来说中转柱是A,对于整个情况三来说中转柱是B。

前面我们已经确定了情况二调用的函数是 move(2,A,B,C),其等价于

这三步,跟情况二的形式是一样的,根据前面情况二的转化,那这三步就可以转化成函数 move(2,A,C,B)

move(2,B,A,C) //step3. 把除了最大的盘子之外的盘子从B移到C

我们又知道情况三调用的函数是 move(3,A,B,C),所以以上三行代码其实就等价于函数 move(3,A,B,C)。

来到这里应该就可以发现一点端倪了,情况四(4层)调用的函数是 move(4,A,B,C),其用伪代码表示就是

move(3,B,A,C) //step3. 把除了最大的盘子之外的盘子从B移到C

对此有怀疑的小伙伴可以自己写出情况四的每步具体步骤然后再做转化,限于篇幅这里不再列出。

那其实可以总结出:对于n(n1)层汉诺塔,调用函数 move(n,A,B,C)来递归解决该问题,该函数执行的是

然后有了以上的理解之后,我们就可以尝试写出解决该问题的代码了,Python实现:

so,读到这里,我大胆猜测大部分人心里应该明白得七七八八了,如果说我猜错了,别急,我们还可以从函数的角度来理解这个问题。

或许有一部分人知道这个函数如何编写,也似懂非懂的了解这个函数注释的意义,但是可能会纠结为什么函数写成这样子就能详细地列出具体的移动步骤(我就是这部分人啊,研究这个问题没少钻牛角尖),下面就跟大家分享下我的另外一个见解。

那么我们必须先将上面3个盘子移动到B,然后再将最大的盘子从A移动到C,接着将在B上的三个盘子从B移动到A才能达到目的。这个过程的关键在于第一步,怎么把上面的3个盘子从A移动到B?

OK,前面说要移动4个就必须先移动上面3个,所以这里我们要移动3个就必须移动上面2个,但是并不是移动到B哦,因为B已经被我们预定好了要用于存放前面移动的3个盘子,如果是将上面2个盘子移动到B,那根据游戏规则第三个盘子就没办法放进去B了,这样子就没办法完成B存放3个盘子的预定目标,所以要移动的上面两个是计划放在C上。

那问题接着就到了该怎么移动上面2个盘子,这时你可能会想要先移走最上面的盘子(这时候要移到B,因为C被我们预定了要存放2个盘子,且B这时候是没有盘子的),没错,那最上面的盘子怎么移?直接移呗怎么移,最上面的盘子都没限制的。所以要移动1个盘子的时候,直接移动: A—B,注意,这个步骤中A为开始柱,B为目标柱。

这时你已经移开最上面的盘子了,就可以把第二盘子移走了,A—C,然后把最小的盘子放到第二个盘子上,B—C,这样就完成了移动2个盘子的任务了。

这三个步骤就是move(2,A,B,C)所做的事情,是可以详细列出每步移动的动作的。

既然最上面的2个盘子都调用move(2,A,B,C)移开了,那么第3个盘子自然也可以从A—B了,之后再把放在C上面的2个盘子从C移动到B上就完成了移动上面3个盘子的任务了。前面的move(2,A,B,C)函数既然可以将2个盘子从A借助B移动到C并列出详细的移动动作,那么move(2,C,A,B)也就能将放在C上的2个盘子从C借助A移动到B并列出详细的移动动作,如此说来,移动3个盘子的步骤就可以总结如下了:

这三个步骤就是move(3,A,C,B)所做的事情,因为我们已经证明move(2,A,B,C)和move(2,C,A,B)是可以详细列出移动2个盘子时每步移动的动作的,而中间的A—B是一步显而易见的移动动作,所以可以确定move(3,A,C,B)是能列出每步的移动动作的。

然后根据同样的分析,最上面的3个盘子都移开了,接着只要将第4个盘子从A—C,然后将放在B上的3个盘子移动到C上就完成全部任务了。前面我们已经证明move(3,A,C,B)能将3个盘子从A借助C移动到B并且列出详细的移动动作,那么move(3,B,A,C)也能将3个盘子从B借助A移动到C并列出每步的移动动作,这样,移动4个盘子的步骤就出来了:

这三个步骤就是最开始move(4,A,B,C)函数所做的事情,因为我们已经证明move(3,A,C,B)和move(3,B,A,C)是可以详细列出移动3个盘子时每步移动的动作的,而中间的A—C是一步显而易见的移动动作,所以可以确定move(4,A,B,C)是能列出每步的移动动作的。

需要说明的是,从xx借助xx移动到xx这样的说法在上面出现了很多次,“从”后面代表的就是开始柱,“借助”后面代表的是中转柱,“移动到”后面代表的是目标柱。你也能注意到到 开始柱,中转柱,目标柱 在不同层级下是不一样的。

根据以上的分析,希望大家就能明白move(n,A,B,C)递归函数的意义了(忘记函数具体内容的往前翻哦)可能有些啰嗦,但是已经尽力表达了我想表达的东西,希望能帮上大家一点忙吧,溜了~

最近收到不少私信咨询了很多关于这个回答更详细的问题,如果大家有任何疑问欢迎私信。

另外答主也感受到了分享知识的快乐,决定投入到知识分享和传递的行列中,所以就弄了个公众号啦,希望能跟大家一起学习,一起进步啊!

发表评论

电子邮件地址不会被公开。 必填项已用*标注