數(shù)據(jù)結(jié)構(gòu)棧與遞歸含分治與回溯

數(shù)據(jù)結(jié)構(gòu)棧與遞歸含分治與回溯第1頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月1、什么是遞歸main函數(shù){……

調(diào)用函數(shù)f……}f函數(shù){……

調(diào)用函數(shù)g……}g函數(shù){………………}f函數(shù){……

調(diào)用函數(shù)f……}遞歸調(diào)用函數(shù)調(diào)用遞歸指函數(shù)直接或間接調(diào)用自己第2頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月intf(intn){intr;if(n==1)r=1;elser=n*f(n-1);returnr;}voidmain(){intx;x=f(5);printf(“%d”,x);}2、為何用遞歸與遞歸執(zhí)行過(guò)程很多問(wèn)題能夠用遞歸的方式描述，此時(shí)采用遞歸算法求解直觀容易，如求階乘：F(1)=1;F(n)=n*F(n-1)3+4*3+3*3+2*6+5*3+11←

6←

2← 1←

24←

120返址nr5671234利用遞歸可方便地解決很多普通方法無(wú)法求解的問(wèn)題第3頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月顯式遞歸問(wèn)題，如求Fibnacci數(shù)列F(n)=F(n-1)+F(n-2)遞歸公式；F(1)=1,F(2)=1邊界條件intf(intn){if(n==1||n==2)r=1;//寫(xiě)f(n)=1錯(cuò)elser=f(n-1)+f(n-2);//注意returnr;}3、如何用遞歸遞歸求解的關(guān)鍵是找邊界條件和遞歸關(guān)系編寫(xiě)遞歸函數(shù)，根據(jù)邊界條件和遞歸關(guān)系是否明顯可將問(wèn)題分為顯示遞歸和隱式遞歸兩類，前者可直接寫(xiě)出遞歸函數(shù)，后者要通過(guò)認(rèn)真分析找到邊界條件，并通過(guò)降階+分治+回溯找遞歸關(guān)系邊界條件遞歸公式第4頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月隱式遞歸—降階EdouardLucas

1842-1891,FrenchABC每次只移一個(gè)盤(pán)大盤(pán)不能壓小盤(pán)類似數(shù)學(xué)歸納法，假設(shè)f(n-1)已知，在此基礎(chǔ)上考慮f(n)的求法,如Hannoi塔問(wèn)題第5頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月XYZ邊界條件: if(n==1)printf(“%c→%c”,x,z);第6頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月XYZ降階:假設(shè)能把n-1個(gè)盤(pán)從一個(gè)位置移動(dòng)到另一個(gè)位置則...hanoi(n,x,y,z);降階：分三步hanoi(n-1,x,z,y);printf(“%c→%c”,x,z);hanoi(n-1,y,x,z);第7頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月遞歸函數(shù)：hanoi(intn,charx,chary,charz)基始條件:if(n==1)printf(“%c→%c”,x,z);降階：分三步hanoi(n-1,x,z,y);printf(“%c→%c”,x,z);hanoi(n-1,y,x,z);xyz第8頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月ABCvoidhanoi(intn,charx,chary,charz){if(n==1)printf(“%c→%c\n”,x,z);else{hanoi(n-1,x,z,y);printf(“%c→%c\n”,x,z);hanoi(n-1,y,x,z);}}voidmain(){hanoi(3,’A’,’B’,’C’);}A→

CA→

BC→

BA→

CB→

AB→

CA→

C第9頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月遞歸函數(shù)中要有使遞歸趨于結(jié)束的邊界條件對(duì)于Fibnacci數(shù)列中F(n)=F(n-1)+F(n-2)形式的遞歸公式，分析求f(5)的過(guò)程可知f(1)被多次重復(fù)調(diào)用，因此原因，求F(40)在Core2T5500CPU上約費(fèi)20秒時(shí)間，故此類問(wèn)題要避免遞歸，需用非遞歸算法改寫(xiě)遞歸—參考書(shū)參考”關(guān)于遞歸教學(xué)的探討.doc”注意事項(xiàng)：第10頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月隱式遞歸—分治--樹(shù)的相關(guān)操作intTreeDepth(TreeT){//求二叉樹(shù)深 if(T==NULL)d=0; else{

d1=TreeDepth(T->lchild1);

d2=TreeDepth(T->rchild);if(d1>d2)

d=d1+1; else d=d2+1; } returnd;}一棵樹(shù)由根結(jié)點(diǎn)、左子樹(shù)及右子樹(shù)組成，對(duì)樹(shù)的操作可分成對(duì)根、左子樹(shù)和右子樹(shù)的操作來(lái)完成！6/5-43-12*+第11頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月隱式遞歸—回溯--8皇后問(wèn)題終態(tài)易判定,遞歸過(guò)程記錄完整解,回溯輸出.Go-Verifyint

Go(intarr[N][N],inti)//逐行處理，當(dāng)前處理編號(hào)為i的行{

intj;

for(j=0;j<N;++j)

{

arr[i][j]=1;//嘗試在第i行的第j列擺下一個(gè)棋子;intsuccessFlag=Verify(arr,i);

if(successFlag==0){arr[i][j]=0;continue;}

elseif(successFlag==1&&i<N-1){//驗(yàn)證合法則前進(jìn)到下一行

//僅當(dāng)從當(dāng)前布局前進(jìn)得不到結(jié)果時(shí)重布局if(Go(arr,i+1)==1)return1;else{arr[i][j]=0;continue;}

}

else{//驗(yàn)證合法且（到達(dá)結(jié)束i=N-1）則輸出解，所有解！

PrintChessBoard(arr);return1;

}

}if(j==N)return-1;}voidmain(){ inta[N][N]={0}; Go(a,0);}第12頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月voidPrintChessBoard(inta[N][N]){ inti,j; for(i=0;i<N;i++) { for(j=0;j<N;j++) { printf("%3d",a[i][j]); } printf("\n"); } printf("\n\n");}intVerify(inta[N][N],inti){ intsum,j,k; for(j=0;j<N;j++)//逐列檢查 { sum=0; for(k=0;k<=i;k++)//看當(dāng)前列前i行中是否沖突 { sum+=a[k][j]; } if(sum>1)return0; } return1;}第13頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月隱式遞歸—回溯（全部解）voidGo(intarr[N][N],inti)//逐行處理，當(dāng)前處理編號(hào)為i的行{

for(intj=0;j<N;++j)

{

arr[i][j]=1;//嘗試在第i行的第j列擺下一個(gè)棋子;successFlag=Verify(arr,i);

if(successFlag==0){arr[i][j]=0;continue;}

elseif(successFlag==1&&i<N-1){//驗(yàn)證合法則前進(jìn)到下一行

Go(arr,i+1);arr[i][j]=0;continue;

//不管成功與否都重置

}

else{//驗(yàn)證合法且到終態(tài)（i=N-1）則輸出解。輸出所有解！

PrintChessBoard(arr);arr[i][j]=0;continue;

}

}}voidmain(){ inta[N][N]={0}; Go(a,0);}第14頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月4、遞歸原理與實(shí)現(xiàn)—棧系統(tǒng)在函數(shù)調(diào)用前完成的工作：將返回地址等信息入棧，并保存本層局部變量值為被調(diào)函數(shù)的局部變量分配存儲(chǔ)區(qū)將控制轉(zhuǎn)移到被調(diào)函數(shù)代碼區(qū)的入口系統(tǒng)在被調(diào)函數(shù)返回之前完成的工作：保存被調(diào)函數(shù)的計(jì)算結(jié)果釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)出棧并根據(jù)返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù),恢復(fù)執(zhí)行遞歸作為函數(shù)調(diào)用特例過(guò)程同上，允許遞歸的語(yǔ)言中系統(tǒng)自動(dòng)維護(hù)一個(gè)遞歸工作棧,不支持遞歸時(shí)用戶可仿照系統(tǒng)自行設(shè)立遞歸工作棧第15頁(yè)，課件共17頁(yè)，創(chuàng)作于2023年2月intf(intn){1intr;2if(n==1)r=1;3elser=n*f(n-1);4returnr;}voidmain(){5intx;6x=f(5);7print(x);}3+4*3+3*3+2*6+5*3+11←

6←

2← 1←

24120返址nr利用棧將遞歸化為非遞歸舉例：intf(intn){

SElemTypee,temp;

SqStackS; InitStack(S); while(n>1){//遞歸前進(jìn)，入棧 e.n=n; Push(S,e); n--; } e.n=1;e.r=1;Push(S,e);//邊界條件 while(!StackEmpty(S)){//