编写一个程序,将自然数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