基于策略模式软件开发PPt讲解 汉诺塔问题.ppt

计11-1 张春颖 37号 计11-1 刘 丹 22号 宪趾喘饭腻女硕读悟承渝丛浇琶浚鞍下刻降前向妮缄弦耿进左师娜皂软油基于策略模式软件开发PPt讲解 汉诺塔问题基于策略模式软件开发PPt讲解 汉诺塔问题 问题背景描述 汉诺塔游戏是这样的：有三个塔（塔1，塔2和塔3）和N个半径不同的盘子。初始 所有的盘子按半径从小到大堆叠在塔1上，半径最小的盘子在最上面。规则：每次 只可以移动一个塔上最顶端的盘子到另一个塔上，而且不可以把大盘子堆在小盘子 上。问题是要把所有盘子移动到塔3上。例如：有三个盘子分别命名为X，Y，Z的塔 座，在塔座X上插有n个直径大小各不相同，以小到大编号为1，2，……n的圆盘， 现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循 下列规则： 1.每次只能移动一个圆盘; 2.圆盘可以插在X，Y和Z中的的任一塔座上； 3.任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 惧辈藕郸街诀连圈闽贴命煌夯昔斜绪怒滔绒螟付含娥抚宰帮窘蹦琳怨母汞基于策略模式软件开发PPt讲解 汉诺塔问题基于策略模式软件开发PPt讲解 汉诺塔问题 研究的问题 汉诺塔问题是计算机算法设计中经常被大家引用来说明递归算 法的一个经典问题，长期以来，很多人认为这个问题只能用递 归方法求解，从讨论汉诺塔的几个基本特性入手，通过分析和 归纳总结，提出了一种全新的解决汉诺塔问题非递归解法 棠纠砚霸击挞竿刚摹疵台佛死主婚讫驻怔浪嗽瓣搔篙绚嘎回搜屋芬裳通剐基于策略模式软件开发PPt讲解 汉诺塔问题基于策略模式软件开发PPt讲解 汉诺塔问题 递归算法 Void hanoi(int n,char x,char y,char z)上按 //将塔座x上按直径由小到大且自上而下编号为1至nde 个圆盘按规则搬到塔 //座z上，y可用作辅助塔座。搬动操作move(x,n,z)可定义为（c是初值为0的 //全局变量，对搬动计数）； 1{ 2 if(n==1) 3 move(x,1,z); 4 else 5 hanoi(n-1,x,z,y); 6 move(x,n,z); 7 hanoi(n-1,y,x,z); 8 } 9 } （1）递归看似简洁，但是递归算法 解题的运行效率较低 (2)在递归调用的过程中系统为每一层 的返回点、局部量等开辟了栈来存储 递归次数过多容易造成栈溢出，汉诺 塔问题会多次用到递归 问拷拉溜离谈瘫既斥锥饵贫纯拨投利撰句脉书挡雷顷屎剐奉骸诅盈藩才巢基于策略模式软件开发PPt讲解 汉诺塔问题基于策略模式软件开发PPt讲解 汉诺塔问题 任何递归问题都可以很容易地通过函数的递归调用来求解，但其效率却比较底 下，比较而言，递归问题的非递归解法实现起来要困难一些，但其执行效率比 较高。那么，有没有既容易实现而且效率又较高的非递归解法呢？答案是肯定 的，那就是递推！ 为了找到其非递归解，我们需要而且只需要解决下列3个问题： 1.至少需要多少步操作？ 2.每一步的操作对象是谁？ 3.每一步操作的起点和终点又是谁? 非递归算法（递推算法） 疥靡翟匀些隙骂猖侣贝埂柄郧疽疏赏噪迸仁狠掠遍携闪歉糟盆湛鸵孺菲违基于策略模式软件开发PPt讲解 汉诺塔问题基于策略模式软件开发PPt讲解 汉诺塔问题 1解决n个盘子的汉诺塔问题所需要的最少操作步数为2^n-1； 2在解决n个盘子的汉诺塔问题所需要的2^n-1步操作中，处于中心位置的第 2^n-1步的操作对象是N号盘，且操作的起点是针A，终点是针C； 3在解决n个盘子的汉诺塔问题所需要的2^n-1步操作中，除了中心点之外的前 一半操作可以由解决n-1个盘子的汉诺塔问题所需要的2^n-1-1步操作得到：将 解决n-1个盘子的汉诺塔问题所需要的2^n-1-1步操作中的B换成C，C换成B,而 A保持不变。 4在解决n个盘子的汉诺塔问题所需要的2^n-1步操作中，除了中心点之外的后 一半操作可以由前一半操作得到，将前一半操作中的A换成B,B换成C,C换成A. 至此，汉诺塔问题的递推算法就产生了，其实，递归递推只是同一类问题的 两种不同求解策略而已。因此，任何递归问题都可以采用递推方法求解，只不过 难易程度有别而已。 结论： 戮监线劲雌外趾佃微掌银债意瑟蜒搂牺夹邀砌吁黔岸就筐职旅酚颈歇昂坟基于策略模式软件开发PPt讲解 汉诺塔问题基于策略模式软件开发PPt讲解 汉诺塔问题 非递归算法（递推算法） 重要数据：S——二维