函數(shù)的遞歸調(diào)用與分治策略-資料下載頁
2025-08-04 15:25本頁面
【正文】 解相當(dāng)多，即使保存到文件中也不現(xiàn)實。這就回答了第2個問題。對于第1個問題，將這個程序略加改動，即賦予全局?jǐn)?shù)組a以初值，并在過程backtrack中產(chǎn)生下一個i和j時跳過有初值的部分，即可將程序轉(zhuǎn)化為求填有部分空缺的九宮格程序。最后給出填充有部分空缺的九宮格的完整源代碼。include iostreamusing namespace std。int a[11][11]={0}。int check(int i,int j,int k){ int l,m,pi,pj。 //1. Check the line for (l=1。l=9。l++) if ( (l!=j) amp。amp。 (a[i][l]!=0) amp。amp。 (a[i][l]==k) ) return(0)。 //2. Check the column for (l=1。l=9。l++) if ( (l!=i) amp。amp。 (a[l][j]!=0) amp。amp。 (a[l][j]==k) ) return(0)。 //3. Check the 3x3 matrix // Firstly we will have to check the parent_i(pi) and parent_j(pj) if (i=3) pi=1。 else if (i=6) pi=4。 else pi=7。 if (j=3) pj=1。 else if (j=6) pj=4。 else pj=7。 // Now we can check it for (l=0。l=2。l++) for (m=0。m=2。m++){ if ( ((pi+l)!=i) amp。amp。 ((pj+m)!=j) ) if ( ( a[pi+l][pj+m]!=0 ) amp。amp。 ( a[pi+l][pj+m]==k ) ) return(0)。 } return(1)。} void output(){ int i,j。 coutOne solution is:endl。 for (i=1。i=9。i++) { for (j=1。j=9。j++) couta[i][j] 。 coutendl。 }}void backtrack(int i,int j,int k){ int l。 if (check(i,j,k)==1) { a[i][j]=k。 //Fill in the okay solution //Generate next i,j do{ if (j9) j++。 else { i++。 j=1。 } } while (a[i][j]!=0)。 //End of Generate next i,j if (i10) { for (l=1。l=9。l++) backtrack(i,j,l)。 } else output()。 a[i][j]=0。 /*When fails and goes upperwards, the value must be cleared*/ }}void init(){ a[1][2]=9。 a[1][6]=4。 a[1][7]=5。 a[1][9]=7。 a[2][3]=3。 a[2][5]=7。 a[2][6]=9。 a[2][7]=4。 a[3][4]=3。 a[3][5]=6。 a[3][8]=8。 a[3][9]=9。 a[4][1]=3。 a[4][4]=1。 a[5][3]=4。 a[5][8]=2。 a[5][9]=3。 a[6][2]=1。 a[6][3]=2。 a[6][6]=3。 a[7][1]=8。 a[7][8]=5。 a[8][2]=6。 a[8][4]=2。 a[8][5]=9。 a[9][2]=2。 a[9][3]=1。 a[9][7]=8。 //memset(a,0,sizeof(a))。}int main(){ int i。 for (i=1。i=9。i++){ init()。 backtrack(1,1,i)。 } system(PAUSE)。 return 0。} 遞歸方法在算法與數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用無所不在，如動態(tài)規(guī)劃（狀態(tài)方程）、回溯法（深度優(yōu)先搜索）等等，以上兩例只是冰山一角。只有熟悉掌握函數(shù)遞歸調(diào)用的編程方法，深入理解分治策略的重要思想，才能編寫出功能強大、高效簡明的程序
物理相關(guān)推薦
鄂ICP備17016276號-1