课程设计汉诺威塔

((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)为左右孩子的二叉树的中序遍历顺序(中序遍历左子树,访问根结点,中序遍历右子树)(见图2)。而左右子树都是n阶汉诺威塔问题,结论也成立。到此证明完毕。Р(图1) 2阶汉诺威塔问题状态树Р(图2) n阶和3阶汉诺威塔问题状态树Р3.流程及程序设计Р3.1流程图:(如下图所示)Р开始Р定义结构体数组M存放盘号和塔座高度Р程序初始化Р输入要演示的盘块数nРn<1||n>10Рn=10Р绘制塔座和盘块Р调用递归函数hanoi( )Рn= =1?Р调用move( )函数将盘块从A移到CР将前n-1个盘块从A移到BР再将A的第n个盘块移到CР最后将B上的n-1个盘移到CР结束Р有上述流程图得出实现递归函数过程的流程图设计如下图所示: