函數(shù)的遞歸調(diào)用與分治策略(參考版)
2024-08-15 15:25本頁面
【正文】 。} 遞歸方法在算法與數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用無所不在，如動(dòng)態(tài)規(guī)劃（狀態(tài)方程）、回溯法（深度優(yōu)先搜索）等等，以上兩例只是冰山一角。 } system(PAUSE)。i++){ init()。 for (i=1。 //memset(a,0,sizeof(a))。 a[9][3]=1。 a[8][5]=9。 a[8][2]=6。 a[7][1]=8。 a[6][3]=2。 a[5][9]=3。 a[5][3]=4。 a[4][1]=3。 a[3][8]=8。 a[3][4]=3。 a[2][6]=9。 a[2][3]=3。 a[1][7]=5。 /*When fails and goes upperwards, the value must be cleared*/ }}void init(){ a[1][2]=9。 } else output()。l=9。 } } while (a[i][j]!=0)。 else { i++。 if (check(i,j,k)==1) { a[i][j]=k。 coutendl。j=9。i=9。 coutOne solution is:endl。 } return(1)。amp。amp。m=2。l=2。 else pj=7。 if (j=3) pj=1。 else if (i=6) pi=4。 (a[l][j]==k) ) return(0)。 (a[l][j]!=0) amp。l++) if ( (l!=i) amp。 //2. Check the column for (l=1。amp。amp。l=9。int check(int i,int j,int k){ int l,m,pi,pj。include iostreamusing namespace std。對(duì)于第1個(gè)問題，將這個(gè)程序略加改動(dòng)，即賦予全局?jǐn)?shù)組a以初值，并在過程backtrack中產(chǎn)生下一個(gè)i和j時(shí)跳過有初值的部分，即可將程序轉(zhuǎn)化為求填有部分空缺的九宮格程序。運(yùn)行時(shí)發(fā)現(xiàn)九宮格的解相當(dāng)多，即使保存到文件中也不現(xiàn)實(shí)。 /*When fails and goes upperwards, the value must be cleared*/ }}函數(shù)output()用雙重循環(huán)完成輸出。 } else output()。l=9。 j=1。 //Fill in the okay solution //Generate next i,j if (j9) j++。將偽代碼翻譯為C++代碼：backtrack(int i,int j,int k){ int l。注意斜體的“a[i,j]:=0”必不可少！當(dāng)對(duì)某個(gè)結(jié)點(diǎn)(x,y)擴(kuò)展的過程中，可能在擴(kuò)展到(x+m,y+n)時(shí)它的子樹被完全殺死（每個(gè)結(jié)點(diǎn)都被殺死，亦即按照(x,y)及之前的填數(shù)方案填數(shù)，無解）。a[i,j]:=0。 if i10 then begin for l:=1 to 9 do backtrack(i,j,l)。 if check(i,j,k)=true then begin a[i,j]=k。如果能一直填到最后一個(gè)數(shù)，結(jié)點(diǎn)仍未被殺死，則這是一個(gè)解。對(duì)下一格，同樣這樣考慮。下面考慮程序最重要的部分，即遞歸函數(shù)。 } return(1)。amp。amp。m=2。l=2。 else pj=7。 if (j=3) pj=1。 else if (i=6) pi=4。 (a[l][j]==k) ) return(0)。 (a[l][j]!=0) amp。l++) if ( (l!=i) amp。 //2. Check the column for (l=1。amp。amp。l=9。函數(shù)check代碼如下：int check(int i,int j,int k){ int l,m,pi,pj。由于我們是按順序填入數(shù)字的，看起來一個(gè)數(shù)字后面的數(shù)字并不在判斷能否填的范圍內(nèi)。為了解決這個(gè)問題，我們需要先編寫一個(gè)函數(shù)check，其原型為int check(int i,int j,int k)，用于求第i行第j列能否填上數(shù)字k。首先考慮如何得出全部解的情況?；厮莘ㄅc純粹的DFS不同的是，它在搜索過程中不斷殺死不合題意的結(jié)點(diǎn)。
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1