一类螺旋方阵问题的算法分析与实现
1 前言
全国青少年信息学（计算机）奥林匹克竞赛常常要用到许多经典算法,比如约瑟夫问题、螺旋方阵、汉诺塔、八皇后问题等,而 螺旋方阵问题是其中较为常用的一种。这类问题的算法分析对于计算机图形学、解析几何中的相关问题都有一定的启发性。尽管现有算法已取得了令人振奋的成绩， 但依然具有一定的片面性，或者说过于复杂。实际上，这个问题有不同的解决算法，鉴于这个问题具有一定的典型性，本文针对信息学奥林匹克竞赛这一问题进行了 全面系统的分析、归纳，从不同的角度对这个问题的算法进行分析并通过程序实现。使读者对这个问题在算法选择上有更大的余地，从而避免算法的单一性，同时对 于类似相关问题的解决也有一定的启发和帮助。
2 问题的描述与分析
关于螺旋方阵的输出主要是指将一些数据或符号按照一定的顺序输出到计算机的屏幕上或者是输出到一个指定的文件中去,输出的几种常见情况如下图(为简单起见,以输出5阶的数字螺旋方阵为例):
|
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 如有不便，请留言提出 14 23 22 21 8 13 12 11 10 9 |
|
1 16 15 14 13 2 17 24 25 12 3 18 25 23 11 义乌信息技术教育,http://www.ywhs.net/itedu 4 19 20 21 10 5 6 7 8 9 |
|
21 22 23 24 25 义乌教育 20 7 8 9 10 义乌信息技术教育,http://www.ywhs.net/itedu
19 6 1 2 11 提供最前沿信息技术教育信息及IT技术 18 5 4 3 12 义乌市信息技术教育网，itedu
17 16 15 14 13 |
|
21 20 19 18 17 如有不便，请留言提出 22 7 6 5 16 23 8 1 4 15 为了仿拷贝，加了这些信息
24 9 2 3 14 25 10 11 12 13 |
如有不便，请留言提出
提供最前沿信息技术教育信息及IT技术
图1由外及里顺时针；图2由外及里逆时针；图3由里及外顺时针；图4由里及外逆时针
在实际应用中,输出的内容可以不尽相同。在上面的图1至图4中，按螺旋顺序输出的数显然有一定的规律，而实际输出的顺序往往不是按照螺旋顺序，通常是将上图中的数据按行（或按列）输出，因此这类问题的关键在于如何将有规律的数据与实际输出时的先后顺序对应起来。下面采用不同的算法来实现。
3 采用不同算法解决螺旋方阵的输出
3．1非递归算法
参照海龟行走的做法，用一对变量A，B模拟海龟头的方向，根据屏幕坐标的特点，A、B的取值和“海龟头”方向有这样的关系：(0,1)表示向右；(0, -1)表示向左；(-1,0)表示向上；(1,0)表示向下；用另一对变量X，Y模拟海龟位置，“海龟”每前进一步，它的新位置即为X=X+A，Y=Y+B；要海龟向右转，就改变A、B的值，根据数学知识可以得出具体的变换公式是：C=A；A=B；B=-C。下面用自然语言对算法进行描述：让海龟先走n步，然后右转，再走n-1步，再右转，再走n-1步，再右转，再走n-2步，再右转，再走n-2步……如此类推，直到海龟前进的步数为0时停止；而每当“海龟”前进1步，就在它位置上显示一个数字，那么前进n步即重复执行“X：=X+A，Y：=Y+B”语句n次。但如何让下两个循环的重复次数都为n-1呢？解决的方法是：循环n次后，让n的值减少0.5，然后再转回执行同样的循环。扩展到显示n位数，则须留n列的位置，也就是说，海龟水平方向每次得前进n步，才有足够的位置显示大一点的数字方阵，需把Y=Y+B改成Y=Y+n*B就行了。“海龟”算法的优点是简洁清晰。
设螺旋方阵对应的一般二维数组如下：
a
提供最前沿信息技术教育信息及IT技术
a
a
a
a
义乌市信息技术教育网，itedu
图5
按逆时针方向从外向内，一层层给下标变量赋值，由于阶数n的任意性，需考虑以下几个问题：层数k与阶数n的关系式，n由用户输入，k根据n来计算；定义变量value,赋值时让其自增；分析每层矩形四条边元素的下标变化规律，将方阵元素按逆时针方向分成四个部分：方阵左半边（三列），方阵下半边（二行），方阵右半边（两列），方阵上半边（二行）。
义乌信息技术教育,http://www.ywhs.net/itedu
具体算法思想：以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 <n-k；i++) mat[i][k]=value++;此循环执行一次，产生一列元素，循环执行的次数由外循环来控制。
Step2：找出方阵下半边行规律：行下标从４变到３，每层取值为n―k―1；列下标由外到内第一行从１变到4（a40已产生），第二行（a30 、a31已产生）从２变到3，第三行只有一个元素a22，故推导出n阶螺旋方阵下半边行循环结构：for(i=k+1；i <n-k；i++) mat[n-k-1][i]=value++;
Step3：找出方阵右半边列规律：行下标第一列从3变化到０（a44已产生），第二列从２变到１（a43、a33、a03已产生），可推断行的初值为n-k-2;列下标没变化，两列的下标分别为４、３，故推断出右半边的列可由下列循环结构完成：for(i=n-k-2；i >=k；i--) mat[i][n-k-1]=value++;
Step4：找出方阵上半边行规律：已经产生了的元素不能再重新赋值，而行下标可用层次k来表示，列下标与右半边行下标变化规律一样，由此推断出上半边的行可由下列循环结构完成：for(i=n-k-2；i >k；i--) mat[k][i]=value++。
当k取一个值时，以上四个循环依序各产生一列或一行元素，由此产生一层元素，当k在变化范围［０…(n+1)/2］内依次取值时，四个循环轮流执行，一个数字螺旋方阵就这样生成了。
为了仿拷贝，加了这些信息
3．2 递归算法
分析图五容易看出，当由外及里顺时针旋转时，最外层数据输出后，内层的图形只不过是层数减少了，即问题的规模变小了，但问题的性质没有发生变化，新问题和原问题仍然可以采用相同的解法。所以这一问题完全可以采用递归的方法来求解。具体的算法描述如下。
为了仿拷贝，加了这些信息
Step1：初始化。把需要输出的数据放入一维数组，设为b[1..n*n]。因为是n阶方阵，所以全部元素共有n2个，输出b[1]到b[n*n]的顺序是方阵顺时针旋转的顺序。
提供最前沿信息技术教育信息及IT技术
Step2：把b数组中的每个元素放入到二维数组a[i][j]（图5）中去，如b[1]放入a[0][0]中，b[2]放入a[0][1]中，……，b[6]放入a[1][4]中……，其它元素依次放入。
Step3：按行输出数组元素a[i][j]即可。
为了仿拷贝，加了这些信息
上述算法中，难点在于如何将b数组放入到a[i][j]数组对应的分量中去。为此，对step2进行求精并使用递归来解决。具体做法：将数组a初始化为0。设置变量direction作为方向标志。当direction为1、2、3、4时，分别表示向右、向下、向左、向上。并编写如下的递归子程序walk(x,y,direction,k)。其中参数x,y表示数组的下标。k是计数器。当 k>n*n 为递归出口。
case direction of
{right } 1： if到右边界then 向下拐 else 向右输出；
{down} 2： if到下边界 then 向左拐 else 向下输出；
提供最前沿信息技术教育信息及IT技术
{left} 3： if到左边界 then 向上拐 else 向左输出；
{up} 4： if 到上边界 then 向右拐 else 向上输出。
如有不便，请留言提出
end;{end case}
3．3 算法实现
限于篇幅，本文仅给出递归算法的主要程序段（pascal语言）
procedure walk(x,y,direction,k:integer);
begin
if k>n*n then 按行输出a数组；
a[x,y]:=b[k];
case direction of
{right}1: if (y=n) or (a[x,y+1]<>0) then walk(x+1,y,2,k+1) else walk(x,y+1,1,k+1);
义乌市信息技术教育网，itedu
{down}2: if (x=n) or (a[x+1,y]<>0) then walk(x,y-1,3,k+1) else walk(x+1,y,2,k+1);
{left} 3: if (y=1) or (a[x,y-1]<>0) then walk(x-1,y,4,k+1) else walk(x,y-1,3,k+1);
{up} 4: if (x=1) or (a[x-1,y]<>0) then walk(x,y+1,1,k+1) else walk(x-1,y,4,k+1)
end;
begin{main}
fillchar(a,sizeof(a),0);
writeln('please input a integer for n:');
readln(n);
为了仿拷贝，加了这些信息
walk(1,1,1,1);
end.{end main}
4 结束语
如有不便，请留言提出
关于螺旋方阵的输出算法主要有上述几种，其他几种方阵的输出，可以仿照上述的算法分析加以实现。相对而言,递 归算法较为简洁，但是时间复杂度要高一些，对于输出高阶螺旋方阵时，时间很长。另外在空间复杂度方面，采用数组这种数据结构，显然有一定的局限性，如果使 用链表来存储，将会尽可能地避免空间不足的现象。另外，上述问题也可以使用一个模板式的子程序来完成，这时要求输入的参数要包括：从外还是从里螺旋、顺时 针还是逆时针，起点坐标等参数，对于从里向外螺旋时，还要考虑螺旋方阵的阶数是奇数还是偶数，分别给予不同的处理。
[1] 潘金贵等 现代计算机常用数据结构和算法[M]，南京大学出版社 1994年3月第1版
[2] William Ford,William Topp[美]著 数据结构C++语言描述[M]，清华大学出版社 2003年5月第1版
[3] 彭月英 n阶螺旋方阵的生成 广西师院学报(自然科学版) 1996.12 第13卷 第4期:1-6
文章评论
共有 0位itedu爱好者发表了评论 查看完整内容