Skip to content Skip to sidebar Skip to footer

如何理解汉诺塔的递归?

作者:梁大炮
链接:https://www.zhihu.com/question/24385418/answer/252603808
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

ps:篇幅稍微有点长,请耐心阅读,相信我,会有价值的。

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

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

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

接着我们分情况讨论一下盘子的移动:

情况一:当盘子只有1个(调用 move(1,A,B,C))

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

情况二:当盘子有2个(调用 move(2,A,B,C))

这个情况分三个步骤进行:

step1. 把除了最大的盘子之外的盘子从A移到B

A—>B (开始柱—>中转柱) 【相当于调用 move(1,A,C,B)】

step2. 把最大的盘子从A移到C

A—>C (开始柱—>目标柱) 【相当于调用 move(1,A,B,C)】

step3. 把除了最大的盘子之外的盘子从B移到C

B—>C (中转柱—>目标柱) 【相当于调用 move(1,B,A,C)】

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

情况三:当盘子有3个(调用 move(3,A,B,C))

这个情况同样分三步进行:

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

A—>C (开始柱—>中转柱) 【相当于调用 move(1,A,B,C)】

A—>B (开始柱—>目标柱) 【相当于调用 move(1,A,C,B)】

C—>B (中转柱—>目标柱) 【相当于调用 move(1,C,A,B)】

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

A—>C (开始柱—>目标柱) 【相当于调用 move(1,A,B,C),即直接执行 print(’A—>C’)】

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

B —> A (开始柱—>中转柱) 【相当于调用 move(1,B,C,A)】

B —> C (开始柱—>目标柱) 【相当于调用 move(1,B,A,C)】

A —> C (中转柱—>目标柱) 【相当于调用 move(1,A,B,C)】

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

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

A—>B

A—>C

B—>C

这三步,然后情况三的step1是

A—>C

A—>B

C—>B

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

情况三的step3同理,做转化就成了函数 move(2,B,A,C)

而情况三的step2可以直接用一句 print(’A—>C’) 来代替 move(1,A,B,C)

所以整个情况三就可以这样来表示:

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

print(’A—>C’) //step2. 把最大的盘子从A移到C

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,A,C,B) //step1. 把除了最大的盘子之外的盘子从A移到B

print(’A—>C’) //step2. 把最大的盘子从A移到C

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

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

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

move(n-1,A,C,B) //step1. 把除了最大的盘子之外的盘子从A移到B

print(’A—>C’) //step2. 把最大的盘子从A移到C

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

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

def move(n,A,B,C):
    if n==1:             # 1个盘子,直接打印出移动动作
        print(A,'--->',C)
    else:                # n > 1时,用抽象出的3步来移动
        move(n-1, A, C, B) #step1.  把除了最大的盘子之外的盘子从A移到B
        print(A,'--->',C) #step2.  把最大的盘子从A移到C
        move(n-1, B, A, C) #step3.  把除了最大的盘子之外的盘子从B移到C

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

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

好,假设现在我们要移动一个4层的汉诺塔,从A—>C:

那么我们必须先将上面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个盘子的任务了。

总结下移动两个盘子的步骤:

A—>B

A—>C

B—>C

这三个步骤就是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(2,A,B,C)

A—>B

move(2,C,A,B)

这三个步骤就是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(3,A,C,B)

A—>C

move(3,B,A,C)

这三个步骤就是最开始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)递归函数的意义了(忘记函数具体内容的往前翻哦)可能有些啰嗦,但是已经尽力表达了我想表达的东西,希望能帮上大家一点忙吧,溜了~

Leave a comment