3.2.3 实践演练——解决“汉诺塔”问题

为了说明递归算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解递归算法思想在编程中的基本应用。

1．问题描述

寺院里有3根柱子，第一根有64个盘子，从上往下盘子越来越大。方丈要求小和尚A1把这64个盘子全部移动到第3根柱子上。在移动的时候，始终只能小盘子压着大盘子，而且每次只能移动一个盘子。

方丈发布命令后，小和尚A1就马上开始了工作，下面看他的工作过程。

（1）聪明的小和尚A1在移动时，觉得很难，另外他也非常懒惰，所以找小和尚A2来帮他。他觉得要是A2能把前63个盘子先移动到第二根柱子上，自己再把最后一个盘子直接移动到第三根柱子上，再让A2把刚才的前63个盘子从第二根柱子上移动到第三根柱子上，整个任务就完成了。所以他找到另一个小和尚A2，然后下了如下命令。

① 把前63个盘子移动到第二根柱子上。

② 把第64个盘子移动到第三根柱子上。

③ 把前63个盘子移动到第三根柱子上。

（2）小和尚A2接到任务后，也觉得很难，所以他也和A1想的一样：要是有一个人能把前62个盘子先移动到第三根柱子上，再把最后一个盘子直接移动到第二根柱子上，再让那个人把刚才的前62个盘子从第三根柱子上移动到第二根柱子上，任务就算完成了。所以他找了另一个小和尚A3，然后下了如下命令。

① 把前62个盘子移动到第三根柱子上。

② 自己把第63个盘子移动到第二根柱子上。

③ 把前62个盘子移动到第二根柱子上。

（3）小和尚A3接到任务后，又把移动前61个盘子的任务“依葫芦画瓢”地交给了小和尚A4，这样一直递推下去，直到把任务交给第64个小和尚A64为止。

（4）此时此刻，任务马上就要完成了，只剩下小和尚A63和A64要做的工作了。

小和尚A64移动第1个盘子，把它移开，然后小和尚A63移动给他分配的第2个盘子。

小和尚A64再把第1个盘子移动到第2个盘子上。到这里A64的任务完成，A63完成了A62交给他的任务的第一步。

2．算法分析

从上面小和尚的工作过程可以看出，只有A64的任务完成后，A63的任务才能完成，只有小和尚A2与小和尚A64的任务完成后，小和尚A1剩余的任务才能完成。只有小和尚A1剩余的任务完成后，才能完成方丈吩咐给他的任务。由此可见，整个过程是一个典型的递归问题。接下来我们以有3个盘子的情况来分析。

具体步骤如下。

（1）第1个小和尚命令第2个小和尚先把第一根柱子上的前2个盘子移动到第二根柱子上（借助第三根柱子）。

（2）第1个小和尚自己把第一根柱子上最后那个盘子移动到第三根柱子上。

（3）第1个小和尚命令第2个小和尚把前两个盘子从第二根柱子移动到第三根柱子上。

显然，第（2）步很容易实现。

其中第（1）步，第2个小和尚有两个盘子，继续执行以下步骤。

① 第3个小和尚把第一根柱子上的第1个盘子移动到第三根柱子上（借助第二根柱子）。

② 第2个小和尚自己把第一根柱子上的第2个盘子移动到第二根柱子上。

③ 第3个小和尚把第1个盘子从第三根柱子移动到第二根柱子上。

同样，上面的第②步很容易实现，但第3个小和尚只需要移动1个盘子，所以他不用再下派任务了（注意：这就是停止递归的条件，也叫边界值）。

第③步可以分解为，第2个小和尚还是有两个盘子，继续执行以下步骤。

（a）第3个小和尚把第二根柱子上的第1个盘子移动到第一根柱子上。

（b）第2个小和尚把第2个盘子从第二根柱子移动到第三根柱子上。

（c）第3个小和尚把第一根柱子上的盘子移动到第三根柱子上。

分析组合起来就是：1→3，1→2，3→2，借助第三根柱子移动到第二根柱子；1→3是懒人留给自己的活；2→1，2→3，1→3是借助别人帮忙，从第一根柱子移动到第三根柱子一共需要七步来完成。

如果是4个盘子，则第一个小和尚的命令中，第①步和第③步各有3个盘子，所以各需要7步，共14步，再加上第1个小和尚的第①步，所以4个盘子总共需要7+1+7=15步；同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=63步……由此可以知道，移动n个盘子需要（2n−1）步。

假设用hannuo(n,a,b,c)表示把第一根柱子上的n个盘子借助第2根柱子移动到第3根柱子上。由此可以得出如下结论：第①步的操作是hannuo(n−1,1,3,2)，第③步的操作是hannuo(n−1,2,1,3)。

3．具体实现

在下面的实例文件hannuo.py中，演示了使用递归算法解决“汉诺塔”问题的过程。

源码路径：daima\第3章\hannuo.py

i = 1
def move(n, mfrom, mto) :
  global i
  print("第%d步:将%d号盘子从%s -> %s" %(i, n, mfrom, mto))
  i += 1
def hanoi(n, A, B, C) :
  if n == 1 :
     move(1, A, C)
  else :
     hanoi(n - 1, A, C, B)
     move(n, A, C)
     hanoi(n - 1, B, A, C)
#********************程序入口**********************
try :
  n = int(input("please input a integer :"))
  print("移动步骤如下：")
  hanoi(n, 'A', 'B', 'C')
except ValueError:
  print("please input a integer n(n > 0)!" )

执行后会输出：

please input a integer :4
移动步骤如下：
第1步:将1号盘子从A -> B
第2步:将2号盘子从A -> C
第3步:将1号盘子从B -> C
第4步:将3号盘子从A -> B
第5步:将1号盘子从C -> A
第6步:将2号盘子从C -> B
第7步:将1号盘子从A -> B
第8步:将4号盘子从A -> C
第9步:将1号盘子从B -> C
第10步:将2号盘子从B -> A
第11步:将1号盘子从C -> A
第12步:将3号盘子从B -> C
第13步:将1号盘子从A -> B
第14步:将2号盘子从A -> C
第15步:将1号盘子从B -> C