汉诺塔问题的递归算法
汉诺塔问题的递归算法
问题简介
汉诺塔问题是一个根据传说形成的数学问题,传说中越南河内的某间寺院里有三根柱子,其中一根上面串有64个盘子,盘子的尺寸由下到上依次变小。要求按照两条规则将所有盘子移动到另一根柱子上:
- 每次只能移动一个圆盘
- 大盘不能叠在小盘上面
以上述规则移动这些盘子,预言说当这些盘子移动完毕,世界就会灭亡,这也就是传说中的梵天寺之塔问题。这个传说的真伪暂且不考虑,我们接下来通过递归的思想通过编程去解决这个问题,给出移动盘子的步骤。
关于递归
递归(Recursion)是一种自己重复自己的过程,一般来说如果一个问题可以拆分为一个与自己一样的小问题的时候,可以通过递归算法进行求解。这样的问题使用递归算法来解决较为便利且代码一般不太复杂,但是递归算法也有自身的缺陷,当我们的问题规模增大的时候,递归算法占用的空间就会成倍增加。
问题分析
我们首先以三阶汉诺塔为例进行举例。将三根柱子依此编号为1,2,3柱,A为起始位置,C为目标位置。在问题的开始,A柱上串有三个盘子,我们将其从小到大称为小,中,大盘。
观察图解过程,我们可以发现问题可以分为三步:
第一步,将小盘和中盘从1挪到2上,对应图解的第1~3步。
第二步,将大盘从1挪到3上,对应图解的第4步。
第三步,再将小盘和中盘从2挪到3上,对应图解的第5~7步。
我们可以看出,第一步和第三步本质上相当于一个二阶汉诺塔问题,第一步以1为起点,2为终点,解决了一个二阶汉诺塔,第三步则变为以2为起点,3为终点。
以此类推,二阶汉诺塔问题则可以分解为两个一阶汉诺塔问题,例如若我们将第一步中小盘与中盘从1挪到2视为一个二阶汉诺塔问题,首先将小盘从1挪到3,然后将中盘从1挪到2,最后将小盘从3挪到2。我们可以将每次小盘的挪动看作一阶汉诺塔问题。至此,汉诺塔的问题就可以通过递归思路实现。
要解决一个N阶汉诺塔,首先解决N-1阶汉诺塔问题,然后将最大的盘子挪到目标柱,最后再解决一次N-1阶汉诺塔问题,而N-1阶汉诺塔问题又可以拆分为两个N-2阶汉诺塔······
代码实现
当明白了汉诺塔问题的本质后,代码实现便异常简单,所以直接给出。
1 |
|