螺旋矩阵算法研究

螺旋矩阵算法研究

作者：魏林

来源：《软件导刊》2014年第10期

摘 要：螺旋矩阵问题是数据结构算法问题中常求解问题之一。介绍了几种常见的螺旋矩阵，对求解螺旋矩阵的两种常用算法进行了详细分析，并在此基础上将算法转化为C语句，对两种算法的时间性能进行了测试分析。结果表明，两种算法的时间复杂度相同，算法执行时间效率也基本一致。

关键词：螺旋矩阵；时间复杂度；C语言 DOIDOI：10.11907/rjdk.143427 中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2014）010005602

作者简介作者简介：魏林（1981-），女，江西九江人，江西经济管理干部学院信息工程系讲师，研究方向为计算机软件技术。 1 螺旋矩阵

螺旋矩阵[1]是指一个呈螺旋形状的矩阵，矩阵的数字从第一行开始至右边不断增大，向下增大，向左增大，向上增大，按此规律循环。按旋转的方向分顺时针、逆时针螺旋矩阵，按数字开始的位置又分为由外向内、由内向外扩散螺旋矩阵，如图1所示。 图1 各种螺旋矩阵

螺旋矩阵的问题常出现在公司面试、学生竞赛试题中，主要考察学生的观察能力、逻辑思维能力及对程序设计的算法设计能力。 2 螺旋矩阵常用算法求解 2.1 按旋转方向构建螺旋矩阵求解

从数字的起始位置开始，沿螺旋矩阵的矩形边框按照旋转的方向（顺时针或逆时针）依次给矩阵的每一个元素赋值，在计算机内存中构造出一个完整的螺旋矩阵，然后将每个矩阵元素顺序输出。以5阶从外到内顺时针螺旋矩阵为例，对应的二维数组如图2所示。

龙源期刊网 http://www.qikan.com.cn

解5阶螺旋矩阵算法思想：按顺时针方向从外向内，一层层给每个下标变量赋值。由于用户输入螺旋矩阵的阶数N具有任意性，因而需要解决以下问题：①层数k与阶数N的关系式；②阶数N由用户输入，层数k应根据N来计算；③定义变量num，赋值后变量num的值自增1，分析每层矩形四条边元素的行标和列标变化规律，将螺旋矩阵元素按顺时针方向分成4个部分：矩阵的上半边（3行），矩阵的右半边（2列），矩阵的下半边（2行），矩阵的左半边（2列）。

图2 按旋转方向构建 图3 坐标求值

5阶螺旋矩阵可判断层数k=N/2=2，用循环控制产生的层数，C语句为for（k=0；k 步骤1：寻找矩阵上半边行的规律（→方向），行下标正好是层数k的值（0、1、2），列下标在第一列从0变到4，第二行从1变到3，在第三行从2变到2，故得出N阶螺旋矩阵上半边从左到右的列循环结构为：for（j=k；j

步骤2：寻找矩阵右半边列的规律（↓方向），列下标从4变到3，行下标由外到内第一列从1变到3，第二列从2变到2，由此得出N阶螺旋方阵右半边列从上到下的循环结构为：for（i=k+1；i

步骤3：寻找矩阵下半边行的规律（←方向），列下标第一行从4变化到1，第二行从3变到2，因此可知行标和列标的初值均为N-k-1，行标没有变化，两行的行标分别为4和3，故得出矩阵下半边的行从右到左的循环结构为：for（j=N-k-1；j >k；j--） a[N-k-1] [j] =num++；当N=5时，层数k从0自增至2，该循环执行2次，产生矩阵下半边两行元素。

步骤4：寻找矩阵左半边行规律（↑方向）：经观察发现，列下标刚好可用层次k来表示，列下标从0变到1，行下标由外到内第一列从4变到1，第二列从3变到2，因此可得出左半边的列从下至上的循环结构为：for（i=N-k-1；i >k；i--） a[i][k]=num++； 当N=5时，层数k从0自增至2，循环执行2次，产生矩阵左半边两列元素。

当用户输入螺旋矩阵的阶数N的值时，层数k确定，当k取一个值时，以上4个循环依序产生一行或者一列矩阵元素，当k值在0至N/2范围内依次取值时，4个循环轮流执行，k值取完后，螺旋矩阵构造完成。 2.2 螺旋矩阵坐标求值求解

以上算法是在构建螺旋矩阵的基础上进行元素赋值，那么能否根据行号和列号直接计算出矩阵元素的值？当用户输入螺旋矩阵的阶数N时，矩阵中每一个元素是唯一的，螺旋矩阵也是唯一的，因此行标和列标必然与元素值之间存在着某种唯一的映射关系。

龙源期刊网 http://www.qikan.com.cn

通过观察，将螺旋矩阵划分成若干个正方形，这些正方形有如下规律，如图3所示。①N为奇数时最内圈是一个点（只有一个元素）；②每一个正方形左上角的元素最小；③每一个正方形上的元素从左上角开始递增；④N阶螺旋矩阵共有（N+1）/2层正方形。

以5阶螺旋矩阵为例，即N=5，设k为正方形的层数编号（k=0，1，2），最外层为第0层，每层的第1个元素值最小，即a（k，k），其对应的值为2*k*（2*N-2*k）+1，如5阶螺旋矩阵的a（0，0）=1；a（1，1）=17；a（2，2）=25。

步骤1：首先确定N阶螺旋矩阵的层数及每层的第1个元素值。用一维数组t[k]来存储每层的第1个元素即每层的最小值，当N为给定值时，螺旋矩阵有（N+1）/2层正方形，需要用到一维数组t[]中N/2+1个元素。如N=5时，螺旋矩阵有3层正方形，需要用到一维数组的t[0]、t[1]、t[2]，值分别为1、17、25，当N=6时，螺旋矩阵仍然有3层正方形，但需要用到一维数组的t[0]、t[1]、t[2]、t[3]，值分别为1、21、33、37。

步骤2：构建双重循环遍历N阶矩阵，设i和j分别为矩阵的行标与列标。

步骤3：根据行标i和列标j的值，确定该元素在哪层正方形上，通过min{i，j，N-i-1，N-j-1}可知某一行列标元素处于第k层正方形上。

步骤4：根据行标i和列标j的值求出该元素所在位置处于螺旋矩阵中的值，分两种情况赋值：①当i≤j时，a[i][j]=t[k]+i+j-2*k；②当i>j时，a[i][j]=t[k+1]-i-j+2*k；。

以上双重循环按矩阵的行列规律遍历了N阶矩阵的每一个元素，在遍历元素的同时并赋予螺旋矩阵的值，当访问完所有元素后，螺旋矩阵便形成。 3 算法时间性能分析

一个算法所耗费的时间，从理论上来讲不能算出来，必须在计算机上运行测试。但不可能、也没有必要对每一个算法都在计算机上测试，只需要知道哪个算法耗费的时间多，哪个算法耗费的时间少，由此来粗略判断算法的优劣。通常情况下，算法所耗费的时间等于算法中每条语句的执行时间之和，而每条语句的执行时间等于语句的执行次数（频度）乘以语句执行一次所需时间[2]。然而，把算法转换为程序后，程序的运行测试将受到计算机的指令性能、运算速度以及编译产生的代码质量等因素的影响，如果忽略这些影响因素，则一个算法的时间耗费就是该算法中所有语句的频度之和，而算法的时间复杂度T（n）就是该算法的时间耗费[3]。基于以上两种算法，分别进行时间复杂度分析。 3.1 按旋转方向构建螺旋矩阵算法关键代码（C语句） for（k=0；k { for（j=k；j

龙源期刊网 http://www.qikan.com.cn

（1） a[k][j]=num++； for（i=k+1；i

（2） a[i][N-k-1]=num++； for（j=N-k-1；j>k；j--） （3） a[N-k-1][j]=num++； for（i=N-k-1；i>k；i--） （4） a[i][k]=num++； }

从语句（1）（2）（3）（4）的内层循环来看，k为最小值0时，各语句频度最大，语句（1）的频度是N-k-1-k+1=N，语句（2）的频度是N-k-1-k-1+1=N-1，语句（3）的频度是N-1，语句（4）的频度是N-1，再看外层循环，外层循环频度为N/2+1因此语句（1）的平均频度为（N/2+1）*N/2，语句（2）（3）（4）的频度均为（N/2+1）*（N-1）/2，因此该程序段频度f（N）= （N/2+1）*（4N-3）/2，该程序段的时间复杂度T（n）=O（n2）。 3.2 坐标求值算法关键程序代码（C语句） for（i=0；i

（1） t[i]=2*i*（N+N-2*i）+1； for（i=0；i { for（j=0；j

（2） { k=min（min（i，j），min（N-1-i，N-1-j））； （3） if（i

（4） else a[i][j]=t[k+1]-i-j+2*k； } }

在坐标求值算法的关键代码中语句（1）位于单层循环内，其频度为N/2，而语句（2）、（3）、（4）都位于双层循环内，语句（2）的频度为（N+1）（N+1），语句（3）和语句

龙源期刊网 http://www.qikan.com.cn

（4）的频度之和为（N+1）（N+1），因此该算法程序段的频度f（N）= N/2+2*（N+1）（N+1），该程序段的时间复杂度也为T（n）=O（n2）。 3.3 算法执行时间效率测试

算法执行时间效率是依据该算法编制的程序在计算机上运行时所消耗的时间来度量。通常度量一个程序的执行时间有两种方法：事前分析估算的方法和事后统计的方法，而算法的时间复杂度研究正是对算法的事前分析估算。于是将两种算法置于VC6.0的测试环境中，通过改变N的大小，得到两个算法消耗的时间量，如表1所示。 4 结语

通过以上分析与测试，按旋转方向构建螺旋矩阵求解算法和坐标求值求解算法的空间复杂度一样，两种算法的执行时间效率也基本一致。虽然螺旋矩阵的问题早已解决，但相同的问题可以用不同算法来解决，因为算法的质量优劣将直接影响到算法乃至程序的执行效率。算法分析的目的是选择合适的算法和改进算法，以最优方法解决问题，因此在螺旋矩阵问题上还需研究者探寻更优的算法。 参考文献

[1] 潘大志，张世禄.螺旋矩阵算法设计与实现[J].电脑开发与应用，2007，20（6）：4041. [2] 严蔚敏，吴伟民.数据结构：C语言版[M].北京：北京清华大学出版社，2007. [3] [美]CORMEN T H.算法导论[M].殷建平，译.北京：机械工业出版社，2013.