汉诺塔递归算法.docx

《汉诺塔递归算法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.5.2汉诺塔递归栈m问题抽象m3个塔，n个碟子m初始：所有碟子放在1号塔，大的在底下，小的在上面m任务：把碟子移动到2号塔，顺序不变，可用3号塔辅助m限制q每次只能移动一个碟子q总是大碟子在下，小的在上m递归解法m移动碟子的方法：move(n,t1,t2,t3)——将n个碟子从t1移到t2，t3辅助m可分解为3个步骤q将n-1个碟子从t1移到t3：move(n-1,t1,t3,t2)q将最大的碟子从t1移到t2q将n-1个碟子从t3移到t2：move(n-1,t3,t2,t1)m汉诺塔递归程序voidTowersOfHanoi(intn,intx,inty,intz){//Movethe

2、topndisksfromtowerxtotowery.//Usetowerzforintermediatestorage.if(n>0){TowersOfHanoi(n-1,x,z,y);cout<<"Movetopdiskfromtower"<

3、归返回的处理q若栈空，整个递归过程结束，跳出循环q否则，将调用者的活动记录弹出栈，恢复其环境，继续循环m递归函数不同入口的区分——返回地址的处理q上例：ENTRANCE、FIRST、SECONDq活动记录的一部分，与参数、局部变量一同压栈、出栈q在循环主体中，根据当前活动记录的入口值，执行不同代码m汉诺塔的递归栈实现#include#include#include#include#includeusingnamespace::std;enum{ENTRANCE=0,FIRST,SECOND};struct

4、ac{intn,x,y,z;intr;};m//汉诺塔的递归栈实现voidhanoi(intn,intx,inty,intz){stackstack;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;}m//汉诺塔递归栈实现if(ac.r==ENTRANCE){stack.push(ac);ac.n--;swap(ac.y,ac.z)

5、;}elseif(ac.r==FIRST){cout<<"Movetopdiskfromtower"<

6、*argv[]){intn;scanf("%d",&n);hanoi(n,1,2,3);return0;}