面向物件的上機實驗
題目
以下列方式向 5*5 矩陣中填入數字，設數字i（1=<i<=25），則數字i+1 的坐標位置應為（E, W），（E, W）可根據下列關系由（x，y）算出：
1）（E, W）=（x±3，y）
2）（E, W）=（x，y±3）
3）（E, W）=（x±2，y±2）
求解問題如下：
撰寫一個程式，當數字1被指定于某個起始位置時，列舉出其它24個數字應在的位置；列舉該條件下的所有可能方案，
參考答案
網上搜索到數學奧賽中本題的Pascal代碼
來自http://blog.sina.com.cn/s/blog_1317189490102vp1k.html
1 Program lx9_1_3; 2 uses crt; 3 const n=5; 4 d:array[1..8，1..2] of shortint=((3，0)，(-3，0)，(0，3)，(0，-3)， 5 (2，2)，(2，-2)，(-2，2)，(-2，-2)); 6 var x0，y0:byte; 7 a:array[1..n，1..n] of byte; 8 total:longint; 9 10 procedure print; 11 var i，j:integer; 12 begin 13 inc(total); 14 gotoxy(1，3); 15 writeln('['，total，']'); 16 for i:=1 to n do 17 begin 18 for j:=1 to n do 19 write(a[i，j]:3); 20 writeln; 21 end; 22 end; 23 24 procedure try(x，y，k:byte); 25 var i，x1，y1:integer; 26 begin 27 for i:=1 to 8 do 28 begin 29 x1:=x+d[i，1];y1:=y+d[i，2]; 30 if (x1>0) and (y1>0) and (x1<=n) 31 and (y1<=n) and (a[x1，y1]=0) then 32 begin 33 a[x1，y1]:=k; 34 if k=n*n then print 35 else try(x1，y1，k+1); 36 a[x1，y1]:=0; 37 end; 38 end; 39 end; 40 41 begin 42 clrscr; 43 write('x0，y0=');readln(x0，y0); 44 fillchar(a，sizeof(a)，0); 45 total:=0;a[x0，y0]:=1; 46 try(x0，y0，2); 47 writeln('Total='，total); 48 writeln('Press any key to exit..，'); 49 repeat until keypressed; 50 end.
自改C語言代碼
運用了深度優先搜索演算法，
可以輸入一個起始位置的坐標后，列舉出所有可能方案和方案個數，
也可以輸出所有初始點方案的個數，
1 #include <stdio.h> 2 #define N 5//格子行列數 3 4 int next[8][2]={{3,0},{-3,0},{0,3},{0,-3},{2,2},{2,-2},{-2,2},{-2,-2}};//下一步變換的位移 5 int x0,y0;//輸入的初始坐標 6 int matrix[N][N];//存盤nxn矩陣中的數字 7 int total;//方案數量 8 9 //列印一個矩陣的函式 10 void printMatrix(){ 11 int i,j; 12 total+=1;//出來一次結果，就列印一次，方案數+1 13 printf("第%d種方案:\n",total); 14 for(i=0;i<N;i++){ 15 for(j=0;j<N;j++){ 16 printf("%4d",matrix[i][j]);//%4d表示輸出寬度為4，且右對齊 17 } 18 printf("\n"); 19 } 20 printf("\n"); 21 } 22 ////每個初始點都輸出方案的個數的話就不把每個方案列印出來了，太占地方 23 //void printMatrix(){ 24 // int i,j; 25 // total+=1;//出來一次結果，就列印一次，方案+1 26 //} 27 28 //主要函式,(x,y)是矩陣內坐標,k是第幾個數字 29 void try(x,y,k){ 30 int i,x1,y1;//x1,y1是本次要找的坐標 31 //將8個位移都試一遍 32 for(i=0;i<8;i++){ 33 x1=x+next[i][0]; 34 y1=y+next[i][1]; 35 //如果該位置不超過邊界且沒有數字，則方案可行，把數字裝進這個位置 36 if((x1>-1)&&(y1>-1)&&(x1<N)&&(y1<N)&&(matrix[x1][y1]==0)){ 37 matrix[x1][y1]=k; 38 //如果k=25即已經搜索完，可以列印了 39 if(k==N*N) 40 printMatrix(); 41 //如果還沒到25，就繼續搜索下一個位置 42 else 43 try(x1,y1,k+1); 44 //本次列印完/本次搜索嘗試到死路，回溯到上一節點去往另一分支前，將這一節點清零 45 matrix[x1][y1]=0; 46 } 47 } 48 } 49 50 51 int main() 52 { 53 //輸入坐標 54 printf("請輸入第一個數的坐標（逗號間隔）："); 55 scanf("%d,%d",&x0,&y0); 56 57 //矩陣整體清0（第一條在dev-c++可以跑,vc++不行，還是用老辦法） 58 //memset(matrix, 0, sizeof(matrix)); 59 int i,j; 60 for(i=0;i<N;i++){ 61 for(j=0;j<N;j++){ 62 matrix[i][j]=0; 63 } 64 } 65 66 //資料初始化，運行 67 total=0;//方案數為零 68 x0-=1;y0-=1;//用戶輸入坐標從1開始，c語言陣列從0開始 69 matrix[x0][y0]=1;//第一個位置賦值1 70 try(x0,y0,2); //從數字2開始放置 71 72 printf("總共有%d種擺放方案\n\n",total); 73 74 75 // //每個初始點都輸出方案的個數 76 // int m,n; 77 // for(m=0;m<5;m++){ 78 // for(n=0;n<5;n++){ 79 // x0=m;y0=n; 80 // //矩陣整體清0 81 // int i,j; 82 // for(i=0;i<N;i++){ 83 // for(j=0;j<N;j++){ 84 // matrix[i][j]=0; 85 // } 86 // } 87 // total=0;//每次節點前方案數清零 88 // matrix[x0][y0]=1;//第一個位置賦值1 89 // try(x0,y0,2); //從數字2開始放置 90 // printf("數字1被指定于(%d,%d)有%d種方案\n",m+1,n+1,total); 91 // } 92 // printf("\n");//每5行之后打個空行好看點 93 // } 94 }
結果
- 輸入一個起始點坐標后輸出的方案
- 輸出所有起始點的方案個數：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137720.html
標籤：其他
上一篇：查找二叉樹
下一篇：圖論篇1——圖的基本概念