一类螺旋方阵问题的算法分析与实现

《一类螺旋方阵问题的算法分析与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要：本文对一类螺旋方阵问题的算法进行了分析，分别从非递归和递归的角度提出了“海龟法”、“分割法”和“递归法”三种算法。关键词：螺旋方阵，算法，递归1　前言-全国青少年信息学（计算机）奥林匹克竞赛常常要用到许多经典算法,比如约瑟夫问题、螺旋方阵、汉诺塔、八皇后问题等,而螺旋方阵问题是其中较为常用的一种。这类问题的算法分析对于计算机图形学、解析几何中的相关问题都有一定的启发性。尽管现有算法已取得了令人振奋的成绩，但依然具有一定的片面性，或者说过于复杂。实际上，这个问题有不同的解决算法，鉴于这个问题具

2、有一定的典型性，本文针对信息学奥林匹克竞赛这一问题进行了全面系统的分析、归纳，从不同的角度对这个问题的算法进行分析并通过程序实现。使读者对这个问题在算法选择上有更大的余地，从而避免算法的单一性，同时对于类似相关问题的解决也有一定的启发和帮助。2　问题的描述与分析关于螺旋方阵的输出主要是指将一些数据或符号按照一定的顺序输出到计算机的屏幕上或者是输出到一个指定的文件中去,输出的几种常见情况如下图(为简单起见,以输出5阶的数字螺旋方阵为例):　图1　　　　　　图2　　　　　　图3　　　　　　图4图1由外

3、及里顺时针；图2由外及里逆时针；图3由里及外顺时针；图4由里及外逆时针在实际应用中,输出的内容可以不尽相同。在上面的图1至图4中，按螺旋顺序输出的数显然有一定的规律，而实际输出的顺序往往不是按照螺旋顺序，通常是将上图中的数据按行（或按列）输出，因此这类问题的关键在于如何将有规律的数据与实际输出时的先后顺序对应起来。下面采用不同的算法来实现。3　采用不同算法解决螺旋方阵的输出3.1非递归算法3.1.1“海龟”算法（顺时针，由外及里）参照海龟行走的做法，用一对变量A，B模拟海龟头的方向，根据屏幕坐标的

4、特点，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时停止；而每当

5、“海龟”前进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就行了。“海龟”算法的优点是简洁清晰。3.1.2“分割”算法（逆时针，由外及里）设螺旋方阵对应的一般二维数组如下：a00a01a02a03a

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

7、+1)/2]=3,用循环控制产生的层数，语句为for(k=0,k<(n+1)/2;k++)。Step1：找出方阵左半边列规律：列下标正好是层数k的值，行下标在第一列从0变到4，第二列从1变到3，在第三列从2变到2，故推导出n阶螺旋方阵左半边由外到内的列循环结构：for(i=k；i

8、40已产生），第二行（a30、a31已产生）从2变到3，第三行只有一个元素a22，故推导出n阶螺旋方阵下半边行循环结构：for(i=k+1；i=k；i--)mat[