矩阵的相关运算——螺旋矩阵

文件:	矩阵的相关运算——螺旋矩阵.rar
大小:	38KB
下载:	下载

 

1   16   15   14   13

 

2   17   24   23   12

 

3   18   25   22   11

 

4   19   20   21   10

 

5   6    7    8     9

 

主要困难：

如何将螺旋矩阵中有规律的数据与实际输出时的先后顺序对应起来。

解决方案：

采用“分割”算法 来解决这个问题。具体思想如下：

    以5阶螺旋方阵为例，对应的二维数组如下：

a00   a01  a02  a03  a04

 

a10  a11  a12  a13  a14

 

a20  a21  a22  a23  a24

 

a30  a31  a32  a33  a34

 

a40  a41  a42  a43  a44

图1

  按逆时针方向从外向内，一层层给下标变量赋值，由于阶数n的任意性，需考虑以下几个问题：层数k与阶数n的关系式，n由用户输入，k根据n来计算；定义变量num,赋值时让其自增；分析每层矩形四条边元素的下标变化规律，将方阵元素按逆时针方向分成四个部分：方阵左半边（三列），方阵下半边（二行），方阵右半边（两列），方阵上半边（二行）。

具体算法思想：以5阶方阵为例，可判断 k=[(n+1)/2]=3,用循环控制产生的层数，语句为for(k=0,k <(n+1)/2;k++)。

 

Step1：找出方阵左半边列规律：列下标正好是层数k的值，行下标在第一列从0变到4，第二列从1变到3，在第三列从2变到2，故推导出n阶螺旋方阵左半边由外到内的列循环结构：for(i=k；i ；i++)  a[i][k]=num++;此循环执行一次，产生一列元素，循环执行的次数由外循环来控制。 

 

Step2：找出方阵下半边行规律：行下标从4变到3，每层取值为n―k―1；列下标由外到内第一行从1变到4（a40已产生），第二行（a30 、a31已产生）从2变到3，第三行只有一个元素a22，故推导出n阶螺旋方阵下半边行循环结构：for(i=k+1；i ；i++) a[n-k-1][i]=num++;

 

 

Step3：找出方阵右半边列规律：行下标第一列从3变化到0（a44已产生），第二列从2变到1（a43、a33、a03已产生），可推断行的初值为n-k-2;列下标没变化，两列的下标分别为4、3，故推断出右半边的列可由下列循环结构完成：for(i=n-k-2；i >=k；i--) a[i][n-k-1]=num++;

 

 

Step4：找出方阵上半边行规律：已经产生了的元素不能再重新赋值，而行下标可用层次k来表示，列下标与右半边行下标变化规律一样，由此推断出上半边的行可由下列循环结构完成：for(i=n-k-2；i >k；i--) a[k][i]=num++。

 

 

当k取一个值时，以上四个循环依序各产生一列或一行元素，由此产生一层元素，当k在变化范围［0…(n+1)/2］内依次取值时，四个循环轮流执行，一个数字螺旋方阵就这样生成了。

 

 

void array(int a[N][N],int n)                //数组函数定义

{

    int p,q;

    int k,m;

    m=(n+1)/2;                               //求螺旋矩阵层数

    int num=1;                               //自增函数初始化

    for(k=0;k                       //用循环控制产生的层数

    {

        for(i=k;i

            a[i][k]=num++;                   //生成左半部数组元素

        for(j=k+1;j

            a[n-k-1][j]=num++;               //生成下半部数组元素

        for(p=n-k-2;p>=k;p--)

            a[p][n-k-1]=num++;               //生成右半部数组元素

        for(q=n-k-2;q>k;q--)

            a[k][q]=num++;                   //生成上半部数组元素

    }

}