汉诺塔递归算法

5.5.2汉诺塔递归栈问题抽象个塔，n个碟子初始：所有碟子放在1号塔，大的在底下，小的在上面任务：把碟子移动到2号塔，顺序不变，可用3号塔辅助限制每次只能移动一个碟子总是大碟子在下，小的在上递归解法移动碟子的方法：move(n,t1,t2,t3)——将n个碟子从t1移到t2，t3辅助可分解为3个步骤将n-1个碟子从t1移到t3：move(n-1,t1,t3,t2)将最大的碟子从t1移到t2将n-1个碟子从t3移到t2：move(n-1,t3,t2,t1)汉诺塔递归程序voidTowersOfHanoi(intn,intx,inty,intz){//Movethetopndisksfromtowerxtotowery.//Usetowerzforintermediatestorage.if(n0){TowersOfHanoi(n-1,x,z,y);coutMovetopdiskfromtowerxtotopoftoweryendl;TowersOfHanoi(n-1,z,y,x);}}-1——最少次数，Θ(2n)一般递归程序转换为循环递归函数主体的转换转换为循环，while(1)即可递归调用的转换将当前参数、局部变量…（活动记录）压栈参照调用方式改变参数，继续循环函数执行结束——递归返回的处理若栈空，整个递归过程结束，跳出循环否则，将调用者的活动记录弹出栈，恢复其环境，继续循环递归函数不同入口的区分——返回地址的处理上例：ENTRANCE、FIRST、SECOND活动记录的一部分，与参数、局部变量一同压栈、出栈在循环主体中，根据当前活动记录的入口值，执行不同代码汉诺塔的递归栈实现#includestdio.h#includestdlib.h#includetime.h#includeiostream#includestackusingnamespace::std;enum{ENTRANCE=0,FIRST,SECOND};structac{intn,x,y,z;intr;};//汉诺塔的递归栈实现voidhanoi(intn,intx,inty,intz){stackstructacstack;structacac={n,x,y,z,ENTRANCE};while(1){if(ac.n=0){if(stack.empty())break;ac=stack.top();stack.pop();if(ac.r==ENTRANCE)ac.r=FIRST;elseac.r=SECOND;}//汉诺塔递归栈实现if(ac.r==ENTRANCE){stack.push(ac);ac.n--;swap(ac.y,ac.z);}elseif(ac.r==FIRST){coutMovetopdiskfromtowerac.xtotopoftowerac.yendl;stack.push(ac);ac.r=ENTRANCE;ac.n--;swap(ac.x,ac.z);}//汉诺塔递归栈实现elseif(ac.r==SECOND){if(stack.empty())break;ac=stack.top();stack.pop();if(ac.r==ENTRANCE)ac.r=FIRST;elseac.r=SECOND;}}}//汉诺塔递归栈实现intmain(intargc,char*argv[]){intn;scanf(%d,&n);hanoi(n,1,2,3);return0;}