汉诺塔答辩ppt.ppt

汉诺塔程序答辩汉诺塔程序答辩第一部分第一部分程序界面程序界面汉诺塔程序演示界面界面设计? private: ? void DrawHanoi (); ? int m_Count ; / / 总移动次数? BITMAP bmpInfo ; / / 位图信息? int m_num ; / / 盘子数? CBitmap bmp[6]; / / 位图分别为背景和五根柱子? void save(int dish[3][5]); ? CList < int,int > AllDish ; / / 容器? int CurDish[3][5]; ? BOOL m_flag ; / / 标志是否第一次调用单步执行在这个演示程序中,我们保留了 windows 经典的窗口栏还有菜单栏,以便用户更直接的对程序进行调试与运行。第二部分第二部分对汉诺塔程序的理解对汉诺塔程序的理解汉诺塔是典型的递归法应用程序?程序调用自身的编程技巧称为递归( recursion )。? 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说, 递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。? 注意: ?(1) 递归就是在过程或函数里调用自身; ?(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。汉诺塔中的递归?如果是三个盘,看成三层楼编号 1,2,3 n=3 时,执行 else , Hannoi(n-1,a,c,b); 在这时调用自己,进入递归第二层,再执行 else , Hannoi(n-1,a,c,b); 这时调用自己,进入第三层,这时因为 n=1, 所以程序执行 if, if(n ==1) Move(1,a,c); 编号 1移动后,跳出递归第三层,回到第二层,这就意味着 n=2 在 Hannoi(n- 1,a,c,b); 这一步执行完毕,往下执行 Move(n,a,c );移动后,执行 Hannoi(n-1,b,a,c); 接着调用 n=1 时,完成后第二层执行完成,跳出,执行 n=3 第一层的 move, 这样一直循环调用,直到 move 被执行 2的 n次方减 1次,完成移动。栈的使用?栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top) ,另一端为栈底(bottom) ;栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈( PUSH ),删除则称为退栈( POP )。栈也称为后进先出表。?栈可以用来在函数调用的时候存储断点,做递归时要用到栈!