數(shù)據(jù)結(jié)構(gòu)課件第三章9講

2023/10/3計(jì)算機(jī)科學(xué)與技術(shù)教研室1/9第9講棧與遞歸3.3遞歸過程及其實(shí)現(xiàn)

1、遞歸的執(zhí)行情況分析

2、TowerofHanoi問題

2023/10/3計(jì)算機(jī)科學(xué)與技術(shù)教研室2/9棧的應(yīng)用過程的嵌套調(diào)用r主程序srrrs子過程1rst子過程2rst子過程32023/10/3計(jì)算機(jī)科學(xué)與技術(shù)教研室3/9例遞歸的執(zhí)行情況分析遞歸過程及其實(shí)現(xiàn)遞歸：函數(shù)直接或間接的調(diào)用自身叫~實(shí)現(xiàn)：建立遞歸工作棧voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;++i)printf(“%3d,”,w);printf(“/n”);}}Ch3_10.c運(yùn)行結(jié)果：1，2，2，3，3，3，2023/10/3計(jì)算機(jī)科學(xué)與技術(shù)教研室4/9遞歸調(diào)用執(zhí)行情況如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)輸出：3,3,3w2print(1);（2）w=2（1）w=3top(3)輸出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)輸出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)輸出：2,2(2)2(1)3top(4)輸出：1(3)1(2)2(1)3top(2)輸出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0結(jié)束(1)2023/10/3計(jì)算機(jī)科學(xué)與技術(shù)教研室5/9TowerofHanoi問題問題描述：有A,B,C三個(gè)塔座，A上套有n個(gè)直徑不同的圓盤，按直徑從小到大疊放，形如寶塔,編號(hào)1,2,3……n。要求將n個(gè)圓盤從A移到C，疊放順序不變，移動(dòng)過程中遵循下列原則：每次只能移一個(gè)圓盤圓盤可在三個(gè)塔座上任意移動(dòng)任何時(shí)刻，每個(gè)塔座上不能將大盤壓到小盤上解決方法：n=1時(shí)，直接把圓盤從A移到Cn>1時(shí)，先把上面n-1個(gè)圓盤從A移到B,然后將n號(hào)盤從A移到C,再將n-1個(gè)盤從B移到C。即把求解n個(gè)圓盤的Hanoi問題轉(zhuǎn)化為求解n-1個(gè)圓盤的Hanoi問題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤的Hanoi問題算法：執(zhí)行情況：遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址返回地址用行編號(hào)表示nxyz返回地址Hanoi.txtHanio視頻演示2023/10/3計(jì)算機(jī)科學(xué)與技術(shù)教研室6/9main(){intm;printf("Inputnumberofdisks”);scanf("%d",&m);printf(”Steps:%3ddisks”,m);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB62023/10/3計(jì)算機(jī)科學(xué)與技術(shù)教研室7/9main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB62023/10/3計(jì)算機(jī)科學(xué)與技術(shù)教研室8/9main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC02023/10/3計(jì)算機(jī)科學(xué)與技術(shù)教研室9/9main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BA