汉诺塔问题

有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆环,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
每次只能移动一个圆盘;大盘不能叠在小盘上面。

提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。

问:如何移?最少要移动多少次?

为了解决这个问题,不妨假设已经知道怎样移动N-1个圆环了。现在,为了把起点盘上的圆环移动到目标盘,需要做如下操作:

1、把N-1个圆环从起点盘移动到(当前)没有任何圆环的过度盘;
2、把最后一个圆环从起点盘移动到目标盘;
3、把N-1个圆环从国度盘移动到目标盘(模仿1和2的操作方法来实现)。

可以借助网友的图示,如果三个圆盘的话:
de285197fc948bae7c46d7e1017173d0.png

如果四个圆盘的话:

de285197fc948b7173d0.png

代码实现如下:

若输入n=3,则结果如下:
7edbdf24b7788be33cd5e6d0790e4332.png

记不住想下面的口诀:递归-句子-递归。
两个盘子:先把小的由A移到B(ACB递归),然后把大的由A移到C(AC句子),然后把小的由B移到C(BAC递归)。