(3.5)--2.1 栈与递归程序设计综合实践.ppt
第二章 递归程序设计汉诺塔问题递归程序设计递归程序执行过程设计递归问题的非递归算法分治法和无符号大数乘法回溯法和八皇后问题、0-1背包问题1一、栈与递归函数相互调用或者递归调用都是通过运行栈实现的。每遇到函数调用，运行栈上分配空间，用于保存下述内容：本次函数调用执行完毕后返回地址；形参变量和函数返回值变量；函数体内局部变量；21.1汉诺塔问题递归程序设计汉诺（Hanoi）塔问题：假设有命名为A、B、C的三个塔柱，初始时，在塔柱A上插有n个直径大小各不相同的圆盘，从上往下，圆盘从小到大编号为1、2、3、n，要求将A柱上的圆盘移至塔柱C，可借助塔柱B，用程序模拟搬盘子过程。圆盘移动必须遵守下列规则：1：每次只能移动一个圆盘；2：圆盘可以插在任意一个塔柱上；3：任何时刻都不能将一个较大的圆盘放在一个较小的圆盘上。3用分治法解决。对于具有n个圆盘的汉诺塔问题，形参x、y、z代表三个塔柱，将x柱上的圆盘移至塔柱z，可借助塔柱y。问题分析如下：n等于1时只需直接将圆盘从x柱移至z柱即可；n大于1时，我们分三步完成：Step1：借助z塔柱，将x塔柱上的n-1个圆盘按照规定移至到y塔柱；Step2：将x塔柱上的一个圆盘由x柱移至z柱；Step3：借助x塔柱，将y塔柱上的n-1个圆盘按规定移至到z塔柱4/Ex2.1 汉诺塔问题完整样例 1#include 2 /将n个盘从x柱搬至z柱，可借助y柱 3 void Hanoi(int n,char x,char y,char z);4 5 int main()6 int n;/盘子数量 7 scanf(%d,&n);8 Hanoi(n,A,B,C);9 return 0;10 5（待续）11 /将n个盘从x柱搬至z柱，可借助y柱 12 void Hanoi(int n,char x,char y,char z)13 14 if(n=1)15 printf(%c-%cn,x,z);/一个盘子时可直接搬动 16 else 17 Hanoi(n-1,x,z,y);/将n-1个盘中从x柱搬至y柱，借助z柱 18 printf(%c-%cn,x,z);/剩余一个盘子时可直接搬动 19 Hanoi(n-1,y,x,z);/将n-1个盘中从y柱搬至z柱，借助x柱 20 21 6汉诺塔问题求解算法时间复杂度和空间复杂度分析。汉诺塔主要操作就是搬盘子，假设n个圆盘的汉诺塔问题求解算法时间复杂度为T(n)，T(1)=1，T(n)=2T(n-1)+1 /n大于1时继续展开：可见，汉诺塔问题求解算法时间复杂度为 。每进入一次Hanoi函数调用，n减小1，汉诺塔问题求解算法递归深度为n，汉诺塔问题求解算法空间复杂度为O(n)。7 1.2递归程序执行过程分析 程序执行过程中遇到的函数调用，包括递归函数调用，都是借助于运行栈来实现的。分析程序执行过程中运行栈变化情况，有助于加深对函数调用实现过程、变量生存期、程序运行过程中内存空间变化情况的理解。以上述汉诺塔问题递归程序Ex2.1执行过程为例，假设样例程序运行时输入3，运行栈变化如图2.1所示。图中S的数值代表函数返回地址，即样例中标示的语句号，n、x、y、z就是程序调用过程中的形参。8 9图2.1 函数递归调用运行栈变化示意图分析得到输出：A-CA-BC-BA-CB-AB-CA-C 10 1.3*等效非递归算法设计 递归算法往往可以借助于栈改写为等效的非递归算法。关键在于确定栈中需要保存什么？一般栈中需要保存代表解题步骤子问题。在设计汉诺塔问题等效非递归算法中，可以由变量n、x、y、z组成的problem代表待解决问题或步骤分解后待解决子问题，开始时设立存放待解决problem类型的空栈，组成待解决问题problem，并入栈；随后循环从栈中取出待解决子问题problem并解决，直到栈为空。在解决从栈中取出待解决子问题problem时，如果子问题problem的规模足够小，如本题中problem.n为1，就可以直接解决；否则，分解子问题problem，形成代表解题步骤、新待解决子问题，如本题中的subProblem1、subProblem2、subProblem3，由于栈的后进先出特点，按解题步骤相反次序将这些子问题入栈，继续循环求解。11/算法2.1将n个盘中从x柱搬至z柱，可借助y柱 1 void NonRecursiveHanoi(int n,char x,char y,char z)2 InitStack(S);/建立问题栈 3 建立n个盘中从x柱搬至z柱，可借助y柱的问题problem;4 S.push(problem);/待解决问题入栈 5 while(!IsEmpty(S)6 problem=gettop(S);/取出栈顶待解决子问题 7 pop(S);/出栈 8 if(problem.n=1)/子问题规模为1，足够小 9 一个盘子时可直接从problem._x到 problem._z搬动 12（待续）10 else 11 /分解获得三个待求解汉诺塔子问题subProblem1,subProblem2,subProblem3 12 建立n-1个盘子从x柱搬至y柱、可借助z柱的子问题subProblem1;13 建立1个盘子从x柱搬至z柱、可借助y柱的子问题subProblem2;14 建立n-1个盘子从y柱搬至z柱、可借助x柱的子问题subProblem3;15 S.push(subProblem3);/最后待求解子问题先入栈 16 S.push(subProblem2);17 S.push(subProblem1);18 19 20 DestroyStack(S);/销毁问题栈 21 13
