由内向外的回旋矩阵研究

由内向外的回旋矩阵研究

题目描述：矩阵从内到外按顺时针旋转的方向递增，如下所示：

   矩阵1（4X5）

   20    7    8    9   10

   19    6    1    2   11

   18    5    4    3   12

   17   16   15   14   13

   矩阵2（5X5）

   21   22   23   24   25

   20    7    8    9   10

   19    6    1    2   11

   18    5    4    3   12

   17   16   15   14   13

本算法旨在研究通过矩阵的行数，列数以及编号求出该编号在矩阵中的位置，如上述矩阵1中5的位置是（2，1），矩阵2中5的位置为（3,1），当然借助本算法就可以对这种类型的回旋矩阵做任何处理。

推理过程：

1.首先，我们发现该矩阵无论是有多少行，多少列，他都有一个东西是不变的，那就是它的拐点处的数值，如下所示（说明：→：表示向右拐；←：表示向左拐；↑：表示向上拐；↓：表示向下拐）：

1→ 2↓ 3← 5↑ 7→ 10↓ 13← 17↑……，我们发现拐点处的数字遵循一定的规律，我们对其进行数学归纳法，发现其是符合下列程式的数列：

a(n) = [ (n-1)(n+2)/4] + 1 - [(n-1)/4] ；（其中 [ (n-1)(n+2)/4]表示不大于(n-1)(n+2)/4的整数，[ (n-1)/4]表示不大于(n-1)/4的整数）

2.然后，我们不难发现，所有的拐点都是按照 → ↓ ← ↑的顺序循环进行的，也就是说4个为一组进行变换，我们还发现组与组之间存在着一种对应关系,假设编号1的拐点在矩阵

中的位置为(x,y),则有如下对应关系：

      第0组               第1组                    ...             第n组

 →   (x,y)              (x-1,y-1)               ...             (x-n,y-n)

 ↓   (x+1,y)         (x+1+1,y-1)           ...             (x+1+n,y-n)

 ←   (x+1,y+1)     (x+1+1,y+1+1)     ...             (x+1+n,y+1+n)

 ↑   (x-1,y+1)      (x-1-1,y+1+1)       ...             (x-1-n,y+1+n)

而我们很容易求出编号为1的拐点在矩阵中的位置，假设矩阵为ROW行COL列，那么1的位置为((ROW-1)/2 , (COL-1)/2)

3.设想，如果我们将所求编号放入拐点数列中，那么我们就能知道该编号位于哪个拐点之后，也可以知道该拐点的拐向及该编号距离该拐点

的偏移量，我们先求出这个拐点在矩阵中的具体位置，然后通过拐点的拐向及该方向的偏移量就可以求出该编号在矩阵中的具体位置。

4.程序代码如下：

#include <iostream.h>

#include<stdio.h>

#include <iomanip.h>

//算法代码

int GetNumbyIndex( int n )//根据数列下标得到数列值

{

int a;

a = ((n-1)*(n+2))/4;

a += 1;

a -= (n-1)/4;

return a;

}

int GetProgressionNo( int* pOff , int nStep )//得到某值相对数列中相对比自己小的值的偏移及该值编号

{

int n;

for ( n = 1; ; n++)

{

if ( GetNumbyIndex(n)<=nStep && GetNumbyIndex(n+1)>nStep)

{

*pOff = nStep - GetNumbyIndex(n);

return n;

}

}

return 0;

}

int GetStepNo( int* pCurRow , int* pCurCol , int nStep , int nRow , int nCol )//得到某值在数列中的行号，列号

{

if ( nStep > nRow*nCol)

return 0;

int nSRow = (nRow-1)/2; //起始行

int nSCol = (nCol-1)/2; //起始列

int nOff = 0;

int nNo = GetProgressionNo( &nOff , nStep); //求出该步在数列的哪一项的后面及偏移量

int nArr = nNo/4; //组别

int nDir = nNo%4; //方向

if ( nDir == 1 ) //右

{

nSCol = nSCol - nArr + nOff;

nSRow = nSRow - nArr ;

}

else if ( nDir == 2 )//下

{

nSCol = nSCol + 1 + nArr ;

nSRow = nSRow - nArr + nOff ;

}

else if ( nDir == 3 )//左

{

nSCol = nSCol + 1 + nArr - nOff ;

nSRow = nSRow + 1 + nArr ;

}

else//上

{

nSCol = nSCol - 1 - (nArr-1) ;

nSRow = nSRow + 1 + (nArr-1) - nOff ;

}

*pCurCol = nSCol;

*pCurRow = nSRow;

return 1;

}

//测试程序

void OutPutArray( int nRow , int nCol)

{

if ( nRow == nCol || nRow + 1 == nCol)

{

int i;

//分配内存

int **pArray = new int* [nRow];

for( i = 0; i < nRow; ++i)

pArray[i] = new int [nCol];

//求出各编号位置并初始化数组

for ( i = 1 ; i <= nRow*nCol ; i++ )

{

int x = 0;

int y = 0;

if ( GetStepNo( &x , &y , i , nRow , nCol ))

{

pArray[x][y] = i;

}

}

//输出

for ( int x = 0 ; x < nRow ; x++ )

{

for ( int y = 0 ; y < nCol ; y++ )

{

cout <<setw(5)<<pArray[x][y];

}

cout<<endl;

}

cout<<endl;

//释放内存

for( i = 0; i < nRow; ++i)

delete []pArray[i];

delete []pArray;

}

}

int main(void)

{

OutPutArray(4,5);

OutPutArray(5,5);

return 0;

}