文档介绍：精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
摘要：
汉诺塔问题源于印度古老的一个塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
A
B
C
汉诺塔
对于一个类似的这样的问题，任何一个人都不可能直接写出移动盘子的每一个具体步骤。可以利用这样的统筹管理的办法求解：我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64。僧人自然会这样想：假如有另外一个僧人能有办法将63个盘子从一个座移到另一个座，那么问题就解决了，此时僧人64只需这样做：
命令僧人63将63个盘子从A座移到C座
自己将最底下的最大的一个盘子从A座移到C座
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
再命令僧人63将63个盘子从B座移到C座
为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一个僧人62能将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座。他是这样做的：
命令僧人62将62个盘子从A移动到C
自己将一个盘子从A座移动到B座
再命令僧人62将62个盘子移到B座
再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成将2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已经完成，都是可以执行的。
按照如此的思路设计递归算法，很容易得出盘子的移动方案。
设A上有n个盘子。
当n=1时，则将圆盘从A直接移动到C。
当n大于等于2时，移动的过程可分解为三个步骤：
第一步 把A上的n-i个圆盘移到B上；
第二步 把A上的一个圆盘移到C上；
第三步 把B上的n-i个圆盘移到C上；其中第一步和第三步是类同的。
为了更清楚地描述算法，用图示法描述如下：
将N个盘子从A杆上借助C杆移动到B杆上。这样移动N个盘子的工作就可以按照以下过程进行：
①第一次调用递归
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
②将一个盘子从A移动到B上；
③第二次调用递归
重复以上过程，直到将全部的盘子移动到位时为止。
由递归算法我们可以得到递推关系：
M(n)=2M(n-1)+1 当n>1时
M(n)=1 当n=1时
下面用归纳法证明n阶汉诺威塔问题，可以用n层二叉树描述，而且它的解就是该二叉树的中序遍历序列。
用一个四元组(n,A,B,C)表示把n个盘子从A搬到C,中间可以借助B的n阶汉诺威塔问题。其中A、B、C的地位是相对的，第一个表示起始位置，最后一个表示终止位置，中间表示过渡位置。例如(n,A,B,C)表示把n个盘子从B搬到C，中间可以借助A的n阶汉诺威塔问题。用一个三元组((n),A,B)表示把第n个盘子从A直接搬到B。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
假设有两个盘子，要把两个盘子从A搬到C，即(2,A,B,C),就必须先把第1个盘子从A搬到B，即((1),A,B),再把第2个盘子从A直接搬到C，即((2),A,C),最后把第1个盘子从B直接搬到C，即((1),B,C),序列((1),A,B),((2),A,C),((1),B,C)正好是以(2,A,B,C)为根，以(1,A,C,B)和(1,B,A,C)为左右孩子的二叉树的中序遍历序列(访问结点时，去掉过渡位置，盘子数加括号)(见图1)，其中双亲结点与左孩子的关系是，盘子个数减1，过渡位置和终止位置交换，与右孩子的关系是，盘子个数减1，起始位置和过渡位置交换。
假如有n个盘子时，结论成立。现在假设有n+1个盘子。要把n+1个盘子从A搬到C，即(n+1,A,B,C)，必须先把前n个盘子从A搬到C，即((n+1),A,C)，最后把前n个盘子从B搬到C，即(n,A,B,C)。序列(n,A,C,B),((n+1),A,C),(n,B,A,C)正好是以(n+1,A,B,C)为根，以(n,A,C,B)和(n,B,A,C)为左右孩子的二叉树的