“蛇形”方阵的构造

        编写一个程序，将自然数1～n² 按“蛇形”填入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且in-1），i=n-1，j=j+2。调整坐标后，再开始从左下向右上填数。

        当从左下到右上时，坐标i减小（i--），坐标j增加（j++），当i减到小于0（副对角线及以上部分从左下到右上填写时），或j加到大于n-1（副对角线以下部分从左下到右上填写时）时结束。然后调整坐标（i,j），调整方法为：当在副对角线及以上时（此时i<0且jn-1），i=i+2，j=n-1。调整坐标后，又开始从右上向左下填数。

        如此循环，直到n*n个数填完为止。

        （2）源程序1。

#include 
#define  N  19
int main()
{
    int a[N][N];
    int n,i=0,j=0,k=1;            // i,j是矩阵元素的下标,k是要填入的自然数
    scanf("%d",&n);
    while(in)
    {
        while(i-1)       // 从右上向左下填数
        { a[i][j]=k++; i++ ;j--; }
        if ((j<0)&&(i0;  // 副对角线及以上部分的新i,j坐标
        else {j=j+2; i=n-1;}    // 副对角线以下的新的i,j坐标.
        while(i>-1 && j// 从左下向右上
        { a[i][j]=k++; i--; j++; }
        if(i<0 && j0;
        else{i=i+2; j=n-1;}
    }
    for (i=0;i)
    {
        for (j=0;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 
#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// 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 
#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)
    {
        for (j=0;j)
            printf("%4d",a[i][j]);
        printf("\n");
    }
    return 0;
}