iiraaa函數(shù)的遞歸調(diào)用與分治策略(參考版)
2025-07-27 11:45本頁面
【正文】 只有熟悉掌握函數(shù)遞歸調(diào)用的編程方法，深入理解分治策略的重要思想，才能編寫出功能強大、高效簡明的程序。 return 0。 backtrack(1,1,i)。i=9。}int main(){ int i。 a[9][7]=8。 a[9][2]=2。 a[8][4]=2。 a[7][8]=5。 a[6][6]=3。 a[6][2]=1。 a[5][8]=2。 a[4][4]=1。 a[3][9]=9。 a[3][5]=6。 a[2][7]=4。 a[2][5]=7。 a[1][9]=7。 a[1][6]=4。 a[i][j]=0。l++) backtrack(i,j,l)。 //End of Generate next i,j if (i10) { for (l=1。 j=1。 //Fill in the okay solution //Generate next i,j do{ if (j9) j++。 }}void backtrack(int i,int j,int k){ int l。j++) couta[i][j] 。i++) { for (j=1。 for (i=1。} void output(){ int i,j。 ( a[pi+l][pj+m]==k ) ) return(0)。 ((pj+m)!=j) ) if ( ( a[pi+l][pj+m]!=0 ) amp。m++){ if ( ((pi+l)!=i) amp。l++) for (m=0。 // Now we can check it for (l=0。 else if (j=6) pj=4。 else pi=7。 //3. Check the 3x3 matrix // Firstly we will have to check the parent_i(pi) and parent_j(pj) if (i=3) pi=1。amp。amp。l=9。 (a[i][l]==k) ) return(0)。 (a[i][l]!=0) amp。l++) if ( (l!=j) amp。 //1. Check the line for (l=1。int a[11][11]={0}。最后給出填充有部分空缺的九宮格的完整源代碼。這就回答了第2個問題。在主函數(shù)main()對backtrack(1,1,i)進行一個循環(huán)，i從1取到9，即可完成整個程序。 a[i][j]=0。l++) backtrack(i,j,l)。 } //End of Generate next i,j if (i10){ for (l=1。 else { i++。 if (check(i,j,k)==1){ a[i][j]=k。這時需要保證(x,y)以后所填的數(shù)被重新置零，這個語句的作用即在每個結(jié)點被殺死時都將其置零。 end。endelse Do_Output。 Generate_next_i_and_j。這種思想可用偽代碼表示如下：procedure backtrack(i,j,k:integer)。不斷用函數(shù)check函數(shù)考察某一個能否填入某數(shù)，一旦函數(shù)check返回0，則殺死這個結(jié)點。思路是這樣的：假設某一格能填入某數(shù)，把這個格子看成解空間樹的一個結(jié)點，由它可以擴展出9個兒子，即下一格填什么數(shù)（由1到9逐個嘗試）。}結(jié)合注釋很容易就能接受函數(shù)的思想，不予過多說明。 ( a[pi+l][pj+m]==k ) ) return(0)。 ((pj+m)!=j) ) if ( ( a[pi+l][pj+m]!=0 ) amp。m++){ if ( ((pi+l)!=i) amp。l++) for (m=0。 // Now we can check it for (l=0。 else if (j=6) pj=4。 else pi=7。 //3. Check the 3x3 matrix // Firstly we will have to check the parent_i(pi) and parent_j(pj) if (i=3) pi=1。amp。amp。l=9。 (a[i][l]==k) ) return(0)。 (a[i][l]!=0) amp。l++)
數(shù)學相關推薦
鄂ICP備17016276號-1