撰寫一個程式，將自然數1～n2 按“蛇形”填入n×n矩陣中，例如，當n=5時，構造的方陣如下，
（1）編程思路1，
分析數的填法，是按“從右上到左下”的”蛇形”或“從左下到右上”的”蛇形”，沿平行于副對角線的各條對角線上，將自然數從小到大填寫，
設用（i,j）表示矩陣元素的坐標，初始時，i=0，j=0，
先從右上到左下填數，當從右上到左下時，坐標i增加（i++），坐標j減小（j--），當j減到小于0（副對角線及以上部分從右上到左下填寫時），或i加到大于n-1（副對角線以下部分從右上到左下填寫時）時結束，然后調整坐標（i,j），調整方法為：當在副對角線及以上時（此時j<0且i<n），j=0；當過副對角線后（此時i>n-1），i=n-1，j=j+2，調整坐標后，再開始從左下向右上填數，
當從左下到右上時，坐標i減小（i--），坐標j增加（j++），當i減到小于0（副對角線及以上部分從左下到右上填寫時），或j加到大于n-1（副對角線以下部分從左下到右上填寫時）時結束，然后調整坐標（i,j），調整方法為：當在副對角線及以上時（此時i<0且j<n），i=0；當過副對角線后（此時j>n-1），i=i+2，j=n-1，調整坐標后，又開始從右上向左下填數，
如此回圈，直到n*n個數填完為止，
（2）源程式1，
#include <stdio.h> #define N 19 int main() { int a[N][N]; int n,i=0,j=0,k=1; // i,j是矩陣元素的下標,k是要填入的自然數 scanf("%d",&n); while(i<n && j<n) { while(i<n && j>-1) // 從右上向左下填數 { a[i][j]=k++; i++ ;j--; } if ((j<0)&&(i<n)) j=0; // 副對角線及以上部分的新i,j坐標 else {j=j+2; i=n-1;} // 副對角線以下的新的i,j坐標. while(i>-1 && j<n) // 從左下向右上 { a[i][j]=k++; i--; j++; } if(i<0 && j<n) i=0; else{i=i+2; j=n-1;} } for (i=0;i<n;i++) { for (j=0;j<n;j++) printf("%4d",a[i][j]); printf("\n"); } return 0; }
（3）編程思路2，
n×n矩陣有2*n-1條平行于副對角線的對角線（下面簡稱為斜線），例如，n=5時，有9條斜線，可將這9條斜線按從上到下用編號k依次標記為1~9，K=5時為副對角線，k<5時，斜線位于副對角線上面，
由題目給出的5×5方陣結果知，該方陣有9條斜線，第1條斜線上填寫1個數，第2條斜線上填寫2個數，…，第5條斜線上填寫5個數，第6條斜線上填寫4個數，…，第9條斜線上填寫1個數，
設第k條斜線上需要填寫的數字個數為q，顯然有
當k<=n時，q=k； 當k>n時，q=2*n-k，
設用（i,j）表示矩陣元素的坐標，1≤i≤n,1≤j≤n，
第k條斜線上的坐標（i,j）一定滿足等式： i+j=k+1
例如，第3條斜線上的3個元素的坐標從右上到左下依次為 （1,3）、（2,2）、（3,1），滿足i+j=k+1=4，同時，可以看出，第3條斜線上的元素坐標i從1到3，
再如，第4條斜線上的4個元素的坐標從左下到右上依次為 （4,1）、（3,2）、（2,3）、（1,4），滿足i+j=k+1=5，同時，可以看出，第4條斜線上的元素坐標j從1到4，
由此，可找出第k條斜線上填寫的q個元素中的第p個元素的坐標（i,j）與k、p、q的關系，
當k為奇數時，斜線上的數字從右上到左下填寫，i=p，j=q+1-p；
當k為偶數時，斜線上的數字從左下到右上填寫，i=q+1-j，j=p，
但當k>n時，此時斜線在副對角線的下方，需要對坐標再修正一下，
例如，第6條斜線上的4個元素的坐標從左下到右上依次為 （5,2）、（4,3）、（3,4）、（2,5），同樣滿足i+j=k+1=7，但是，第6條斜線上的元素坐標j從2到5，i從5遞減到2，而按上面的關系計算出的第6條斜線上的元素坐標j從1到4，i從4遞減到1，此時，只需要將計算出的坐標i和j的值均加上1（也即n-q）即可，
同樣，考察第7條斜線上的3個元素的坐標從右上到左下依次為 （3,5）、（4,4）、（5,3），同樣滿足i+j=k+1=8，但是，第7條斜線上的元素坐標i從3到5，j從5遞減到3，而按上面的關系計算出的第7條斜線上的元素坐標i從1到3，j從3遞減到1，此時，只需要將計算出的坐標i和j的值均加上2（也即n-q）即可，
計算出了每條斜線上應該填寫的每個元素的坐標，在該坐標位置填上相應的數字，采用回圈將這2*n-1條斜線上均填寫上數字，則“蛇形”方陣就可以構造完成，
（4）源程式2，
#include <stdio.h> #define N 20 int main() { int a[N][N]; int n,i,j,k=1,m,p,q; scanf("%d",&n); m=1; // m是要填入的自然數 for (k=1;k<2*n; k++) // 第k條平行與副對角線的對角線 { if (k<n) q=k; // q是第k條對角線上填寫數字的個數 else q=2*n-k; for (p=1;p<=q;p++) { if (k%2) { i=p; j=q+1-p;} else { i=q+1-p; j=p; } if (k>n) { i=i+n-q; j=j+n-q; } a[i][j]=m++; } } for (i=1;i<=n;i++) { for (j=1;j<=n;j++) printf("%4d",a[i][j]); printf("\n"); } return 0; }
（5）編程思路3，
觀察圖1所示的蛇形陣可知，方陣在逐個填數構造的程序中，是沿兩種斜線進行的，一種是“右上到左下”（斜向下），一種是“左下到右上”（斜向上），
圖1 蛇形方陣的構造示意圖
設當前已填入數字的位置坐標為（i,j），i和j均在0~n-1之間，若按斜向下填寫，則下一位置為row++、col-- ；若按斜向上填寫，則下一位置為row--、col++，由于下一位置可能超出方陣的邊界，因此有時需要調整，調整有4種情況，下面分別進行說明，
斜向上填寫時，會出現兩種情況：
（1）超過了首行的位置（即i==-1），如圖1（a）所示，3填寫好后，下一個數4的計算位置越界了，此時進行調整，方法為i++，
（2）超過最右列的位置（即j==n），如圖1（b）所示，19填寫好后，下一個數20的計算位置越界了，此時進行調整，方法為i+=2、j--，
一種特例，在如圖1（c）所示的4階方陣中，10填寫好后，下一個數11的計算位置，行和列都越界了，其處理方法同列越界，因此在程式中應先處理j==n的情況，再處理i==-1的情況，這樣對于這種特例，由于處理了j==n后，i加了2，不會越界，因此不會再處理i==-1的情況，
斜向下填寫時，也會出現兩種情況：
（1）超過最左列的位置（即j==-1），如圖1（d）所示，6填寫好后，下一個數7的計算位置越界了，此時進行調整，方法為j++，
（2）超過了底行的位置（即 i==n），如圖1（e）所示，22填寫好后，下一個數23的計算位置越界了，此時進行調整，方法為 i--,j+=2，
一種特例，15填寫好后，下一個數16的計算位置，行和列都越界了，但處理方法同行越界，因此在程式中應先處理i==n的情況，再處理j==-1的情況，這樣對于這種特例，由于處理了i==n后，j加了2，不會越界，因此不會再處理j==-1的情況，
每次進行越界調整填數后，填數的方向也會發生變化，因此，可設定一個方向變數up，當up=1時，表示斜向下填數；up=0時，表示斜向上填數，
初始化時，令up=1、i=0、j=0；在當前位置填上1（即a[i][j]=1），之后從 m=2開始進行回圈，直到m==n*n，全部n*n個數填寫完畢，回圈中，總是先按up的方向，確定下一個位置，然后填上相應的數，
（6）源程式3，
#include <stdio.h> #define N 20 int main() { int a[N][N]; int n,i,j,m; scanf("%d",&n); int up=1; i=0; j=0; a[i][j]=1; m=2; // m是要填入的自然數 while (m<=n*n) { if (up) { i++; j--; } // 從右上到左下 else { i--; j++; } // 從左下到右上 if (j==n) // 超過最右列的位置 { i=i+2; j--; up=!up; } if (i==-1) // 超過首行的位置 { i++; up=!up; } if (i==n) // 超過底行的位置 { i--; j+=2; up=!up; } if (j==-1) // 超過最左列的位置 { j++; up=!up; } a[i][j]=m++; } for (i=0;i<n;i++) { for (j=0;j<n;j++) printf("%4d",a[i][j]); printf("\n"); } return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/537683.html
標籤：其他
上一篇：電視劇里的代碼真能運行嗎？