汉诺塔？

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘……

以上内容摘自百度百科

回归正题，笔者最近在回顾递归概论时看到了这道经典问题，这估计也是最有名的递归问题之一。
递归算法的优势在于结构，但其中结构逻辑又往往令人头痛欲裂。
本文是笔者为个人在实现算法过程中的逻辑梳理;
(因递归特性，先理清递归逻辑与工作栈对于实现过程是必要的，这里笔者使用的是经典分治法)。
下面开始吧(qwq)

算法问题

汉诺塔的规则有三点：
1.每次只能移动一个圆盘。
2.圆盘可以插在任意一个柱上。
3.任何时刻大号圆盘都不能在小号圆盘上。

算法目的就是遵循规则前提下按照原来顺序将处在A柱上的圆盘转移到C柱上

思路

乍一看好像这是个挺简单的问题？
让我们先来进行初次移动试试：

这里我们定义一个4阶汉诺塔(限于语法以及笔者懒此处采用文字图表来表示):

A.4 3 2 1
B.
C.

此时A塔上4个圆盘成栈排列。
我们要保证C的圆盘进入和A的圆盘序列为栈性相关，并且还要遵从规则3，由此可见我们得将3 2 1号圆盘移动到b上。

但这位时候问题又来了：
3 2 1号圆盘的移动也必须要遵从规则3，*(为了移动3号圆盘到B)*从而必须将2 1号圆盘移动到C柱(关于过渡，下文有说明)；
同样的，2 1号圆盘的移动也必须将1号圆盘移动到B柱；

感觉上这是一个递归逻辑，为了检验
于是我们来操作一下：

步骤

(为了简化叙述，移动操作将用”1A->B”(将A柱上的1号圆盘移动到B盘)来表示)
1|1A->B

A.4 3 2
B.1
C.

2|2A->C

A.4 3
B.1
C.2

3|1B->C

A.4 3
B.
C.2 1

4|3A->B

A.4
B.3
C.2 1

(这里下一步就是要将2 1号圆盘移动到B柱上，而移2先移1；2 1号盘在C柱上，B柱为目标柱，故A柱为过渡)

5|1C->A

A.4 1
B.3
C.2

6|2C->B

A.4 1
B.3 2
C.

7|1A->B

A.4
B.3 2 1
C.

(现在移动4号圆盘)

8|4A->C

A.
B.3 2 1
C.4

至此，我们完成了第一步的操作，将4号圆盘移动到C柱上；而4号圆盘为栈底盘，故后续不会再对其进行操作。
那么这样一来，我们便可以将4号盘忽视掉，于是我们再次审视这个汉诺塔：

A.
B.3 2 1
C.4

wc

不难发现，如果把B柱看成初始柱,即：

A(原B).3 2 1
B(原A).
C.4

这不就是一个3阶汉诺塔吗？
也就是说，经过上面的8步操作，我们将这个4阶汉诺塔转化成了3阶级汉诺塔。
于是我们便有了思路：

将上述步骤定义为方法Hanoi，调用对象为n阶汉诺塔；每调用一次Hanoi，会将对象转化成n-1阶汉诺塔。

当对象变为1阶汉诺塔后，只需一步便可完成解题。

于是我们将调用方法Hanoi处理n阶汉诺塔并将输出对象再次调用Hanoi，直至得到1阶汉诺塔。

外部问题我们已经理清了，接下来我们该思考方法Hanoi的实现了。

这里我们采用分治法思考：

  • Hanoi操作的实质其实是将n号圆盘移动到C柱，而移动n号圆盘就必须移动1~n-1号圆盘；

    • 移动n-1号圆盘就必须先移动1~n-2号圆盘；

      • 由此递推……

不难发现我们是在执行一个每层问题规模-1的相同嵌套操作，这样我们就可以将其转化为一个递归问题。

**1.将A柱上1~n-1号圆盘移动到B

Hanoi全体步骤

1.移动1~n-1号圆盘到B柱，C柱为过渡

2.移动n号圆盘到C柱

3.移动1-n-2号圆盘到A柱，C柱为过渡

4.移动n-1号圆盘到B柱

……

Final.移动1号圆盘到C柱

上述奇数步便为递归操作，以1为例，即为Hanoi前7步拓展:

待更新(好累)