第ｌ ３卷第ｌＯ期 ２０１４年１０月 软件导刊 Ｓｏｆｌｗａｒｅ Ｇｕｉｄｅ 、－０１．１３ＮＯ．ＪＯ ０ｃｔ．２Ｏｌ４ 螺旋矩阵算法研究 魏 林 （江西经济管理干部学院信息工程系，江西南昌３３００８８） 摘 要：螺旋矩阵问题是数据结构算法问题中常求解问题之一。介绍了几种常见的螺旋矩阵，对求解螺旋矩阵的两 种常用算法进行了详细分析，并在此基础上将算法转化为Ｃ语句，对两种算法的时间性能进行了测试分析。结果表 明，两种算法的时间复杂度相同．算法执行时间效率也基本一致。 关键词：螺旋矩阵；时间复杂度；ｃ语言 ＤＯＩ：１０．１１ ９０７／ｒｊｄｋ．１４３４２７ 中图分类号：ＴＰ３ｌ２ 文献标识码：Ａ 文章编号：１６７２—７８００（２０ｌ４）Ｏ１Ｏ－００５６—０２ 阵元素按顺时针方向分成４个部分：矩阵的上半边（３ １ 螺旋矩阵 螺旋矩阵 。是指一个呈螺旋形状的矩阵，矩阵的数字 从第一行开始至右边不断增大，向下增大，向左增大，向上 增大，按此规律循环。按旋转的方向分顺时针、逆时针螺 旋矩阵，按数字开始的位置又分为由外向内、由内向外扩 行），矩阵的右半边（２列），矩阵的下半边（２行），矩阵的左 半边（２列）。 ａ００ ０１ ．１０２＂，１０３ ａ０ 散螺旋矩阵，如图１所示。 ｌ ２ ３ ８ ９ ４ ７ ６ ５ １ ８ ２ ９ ６ ３ ４ ５ ７ ８ ９ ６】２ ５ ４ ３ ９ ８ ７ ２】６ ３ ４ ５ 置 ｌ ＾： ｌ３ ＾｝ 图３坐标求值 图２按旋转方向构建 从外到内顺时针 从外到内逆时针 从内至 顺时针 从内到外逆时针 ５阶螺旋矩阵可判断层数ｋ—Ｎ／２—２，用循环控制产 生的层数，Ｃ语句为ｆｏｒ（ｋ一０；ｋ＜一Ｎ／２；ｋ＋＋）；。 步骤１：寻找矩阵上半边行的规律（一方向），行下标 图ｌ各种螺旋矩阵 螺旋矩阵的问题常出现在公司面试、学生竞赛试题 中，主要考察学生的观察能力、逻辑思维能力及对程序设 计的算法设计能力。 正好是层数ｋ的值（０、１、２），列下标在第一列从０变到４， 第二行从ｌ变到３，在第三行从２变到２，故得出～阶螺旋 矩阵上半边从左到右的列循环结构为：ｆｏｒ（ｊ—ｋ；ｊ＜一Ｎ ２螺旋矩阵常用算法求解 ２．１ 按旋转方向构建螺旋矩阵求解 ｋ—ｌ；ｊ４－＋）ａＥｋ］［ｊ］一ｎｕｍ＋＋；该循环执行一次将产 生一行元素，而循环执行的次数由外层循环来予以控制， 当Ｎ：５时，层数ｋ从０自增至２．循环执行共３次，将产 从数字的起始位置开始，沿螺旋矩阵的矩形边框按照 旋转的方向（顺时针或逆时针）依次给矩阵的每一个元素 生螺旋矩阵的上半边３行元素。 步骤２：寻找矩阵右半边列的规律（ 方向），列下标 从４变到３，行下标由外到内第一列从１变到３，第二列从 赋值，在计算机内存中构造出一个完整的螺旋矩阵，然后 将每个矩阵元素顺序输 。以５阶从外到内顺时针螺旋 矩阵为例，对应的二维数组如图２所示。 解５阶螺旋矩阵算法思想：按顺时针方向从外向内， 一２变到２，由此得出Ｎ阶螺旋方阵右半边列从上到下的循 环结构为：ｆｏｒ（ｉ—ｋ＋１；ｉ＜Ｎ—ｋ—ｌ；ｉ＋＋）ａＥｉ］ＩＮ—ｋ一 １］一ｈｕｍ＋＋；当Ｎ一５时，层数ｋ从０自增至２，该循环 层层给每个下标变量赋值。由于用户输入螺旋矩阵的 阶数Ｎ具有任意性，因而需要解决以下问题：①层数ｋ与 阶数Ｎ的关系式；②阶数Ｎ由用户输入，层数ｋ应根据Ｎ 执行２次，产生矩阵右半边两列元素。 步骤３：寻找矩阵下半边行的规律（一方向），列下标 第一行从４变化到１，第二行从３变到２，因此可知行标和 列标的初值均为Ｎ—ｋ一１，行标没有变化，两行的行标分 来计算；③定义变量ｎＵＩＴＩ，赋值后变量ｒｌｕｍ的值白增１。分 析每层矩形四条边元素的行标和列标变化规律，将螺旋矩 作者简介：魏林（１９８１一）。女。江西九江人，江西经济管理干部学院信息工程系讲师，研究方向为计算机软件技术。 第１Ｏ期 魏林：螺旋矩阵算法研究 ·５７· 别为４和３，故得出矩阵下半边的行从右到左的循环结构 为：ｆｏｒ（ｊ：Ｎ—ｋ一１；ｊ ｉ＞ｋ；ｊ一一）ａ［Ｎ—ｋ一１］［ｊ］一ｎｕｒｎ ＋４－；当Ｎ一５时，层数尼从０自增至２，该循环执行２次， 产生矩阵下半边两行元素。 步骤４：寻找矩阵左半边行规律（十方向）：经观察发 现，列下标刚好可用层次矗来表示，列下标从０变到１，行 下标由外到内第一列从４变到１，第二列从３变到２，因此 可得出左半边的列从下至上的循环结构为：ｆｏｒ（ｉ—Ｎ—ｋ ～１；ｉ＞ｋ；ｉ－－一）ａＥｉ］Ｅｋｌ—ｎｕｍ＋＋；当Ｎ一５时，层数忌 从０自增至２，循环执行２次，产生矩阵左半边两列元素。 当用户输入螺旋矩阵的阶数Ｎ的值时，层数走确定， 当五取一个值时，以上４个循环依序产生一行或者一列矩 阵元素，当矗值在０至Ｎ／Ｚ范围内依次取值时，４个循环 轮流执行，忌值取完后，螺旋矩阵构造完成。 ２．２螺旋矩阵坐标求值求解 以上算法是在构建螺旋矩阵的基础上进行元素赋值， 那么能否根据行号和列号直接计算出矩阵元素的值？当 用户输入螺旋矩阵的阶数Ｎ时，矩阵中每一个元素是唯 一的，螺旋矩阵也是唯一的，因此行标和列标必然与元素 值之间存在着某种唯一的映射关系。 通过观察，将螺旋矩阵划分成若干个正方形，这些正 方形有如下规律，如图３所示。①Ｎ为奇数时最内圈是一 个点（只有一个元素）；②每一个正方形左上角的元素最 小；③每一个正方形上的元素从左上角开始递增；④Ｎ阶 螺旋矩阵共有（Ｎ＋１）／Ｚ层正方形。 以５阶螺旋矩阵为例，即Ｎ一５，设忌为正方形的层数 编号（是一０，１，２），最外层为第０层，每层的第１个元素值 最小，即ａ（ｋ，是），其对应的值为２＊尼＊（２＊～一２＊忌）－５ １，如５阶螺旋矩阵的ａ（０，０）一１；ａ（１，１）：１７；ａ（２，２）一 ２５。 步骤１：首先确定Ｎ阶螺旋矩阵的层数及每层的第１ 个元素值。用一维数组￡［愚］来存储每层的第１个元素即 每层的最小值，当Ｎ为给定值时，螺旋矩阵有（Ｎ＋１）／ｚ 层正方形，需要用到一维数组￡［］中Ｎ／Ｚ＋１个元素。如 Ｎ一５时，螺旋矩阵有３层正方形，需要用到一维数组的ｔ ［Ｏ］、ｔ［１］、ｔＥｚｌ，值分别为１、１７、２５，当Ｎ一６时，螺旋矩阵 仍然有３层正方形，但需要用到一维数组的ｔ［０］、ｔＥ１］、ｔ ［２］、ｔＥ３１，值分别为１、２１、３３、３７。 步骤２：构建双重循环遍历Ｎ阶矩阵，设ｉ和 分别 为矩阵的行标与列标。 步骤３：根据行标ｉ和列标 的值，确定该元素在哪层 正方形上，通过ｍｉｎ｛ｉ，Ｊ，Ｎ—ｉ一１，Ｎ— 一１｝可知某一行 列标元素处于第愚层正方形上。 步骤４：根据行标 和列标 的值求出该元素所在位 置处于螺旋矩阵中的值，分两种情况赋值：①当 ≤ 时，ａ ＥｉＪＥｊ］一ｔ［ｋ］＋ｉ＋ｊ－－２＊ｋ；②当ｉ＞ｊ时，ａＥｉｌ［ｊｌ：ｔ［ｋ＋１］ ｉ～ｊ＋２＊ｋ；。 以上双重循环按矩阵的行列规律遍历了Ｎ阶矩阵的 每一个元素，在遍历元素的同时并赋予螺旋矩阵的值，当 访问完所有元素后，螺旋矩阵便形成。 ３算法时间性能分析 一个算法所耗费的时间，从理论上来讲不能算出来， 必须在计算机上运行测试。但不可能、也没有必要对每一 个算法都在计算机上测试，只需要知道哪个算法耗费的时 间多，哪个算法耗费的时间少，由此来粗略判断算法的优 劣。通常情况下，算法所耗费的时间等于算法中每条语句 的执行时间之和，而每条语句的执行时间等于语句的执行 次数（频度）乘以语句执行一次所需时间口 。然而，把算法 转换为程序后，程序的运行测试将受到计算机的指令性 能、运算速度以及编译产生的代码质量等因素的影响，如 果忽略这些影响因素，则一个算法的时间耗费就是该算法 中所有语句的频度之和，而算法的时间复杂度Ｔ（ｎ）就是 该算法的时间耗费口 。基于以上两种算法，分别进行时间 复杂度分析。 ３．１ 按旋转方向构建螺旋矩阵算法关键代码（Ｃ语句） ｆｏｒ（ｋ一０；ｋ＜一Ｎ／２；ｎ＋＋） ｛ｆｏｒ（ｊ—ｋ；ｊ＜一Ｎ—ｋ—ｌ；ｊ＋＋） （１）ａ［ｋ］［ｊ］一ｎｕｍ＋＋； ｆｏｒ（ｉ—ｋ＋１；ｉ＜Ｎ—ｋ一１；ｉ＋＋） （２）ａ［ ］［Ｎ—ｋ一１］：ｎｕｍ＋＋； ｆｏｒ（ｊ—Ｎ—ｋ一１；ｊ＞ｋ；ｊ～一） （３）ａ［Ｎ—ｋ一１］［ｊ］一ｎｕｍ＋＋； ｆｏｒ（ｉ—Ｎ—ｋ—ｌ；ｉ＞ｋ；ｉ一一） （４）ａ［ｉ］［ｋ］一ｎＨｍ＋＋；） 从语句（１）（２）（３）（４）的内层循环来看，是为最小值０ 时，各语句频度最大，语句（１）的频度是Ｎ一是一１一是＋１一 Ｎ，语句（２）的频度是Ｎ一志一１一点一１＋１一Ｎ一１，语句 （３）的频度是Ｎ一１，语句（４）的频度是Ｎ一１，再看外层循 环，外层循环频度为Ｎ／Ｚ十１因此语句（１）的平均频度为 （Ｎ／２＋１）＊Ｎ／Ｚ，语句（２）（３）（４）的频度均为（Ｎ／Ｚ＋１）＊ （Ｎ一１）／Ｚ，因此该程序段频度＿厂（Ｎ）一（Ｎ／２４－１）＊（４Ｎ 一３）／２，该程序段的时间复杂度Ｔ（ ）一Ｏ（ｎ ）。 ３．２坐标求值算法关键程序代码（Ｃ语句） ｆｏｒ（ｉ一０；ｉ＜（Ｎ／２＋１）；ｉ＋＋） （１）ｔ［ｉｌ一２＊ｉ＊（Ｎ＋Ｎ一２＊ｉ）＋１； ｆｏｒ（ｉ一０；ｉ＜Ｎ；ｉ＋＋） ｛ｆｏｒ（ｊ一０；ｊ＜Ｎ；ｊ＋＋） （２）｛ｋ—ｒａｉｎ（ｒａｉｎ（ｉ，ｊ），ｒａｉｎ（Ｎ一１一ｉ，Ｎ一１－－ｊ））； （３） ｉｆ（ｉ＜一ｊ）ａ［ｉ］［ｊ］一ｔＥｋｌ＋ｉ＋ｊ一２＊ｋ； （４） ｅｌｓｅ ａＥｉｌＥｊ￣一ｔ［ｋ＋１］一ｉ—ｊ＋２＊ｋ； ｝ ｆ 在坐标求值算法的关键代码中语句（１）位于单层循环 内，其频度为Ｎ／２，而语句（２）、（３）、（４）都位于双层循环 内，语句（２）的频度为（Ｎ＋１）（Ｎ＋１），语句（３）和语句（４） 的频度之和为（Ｎ＋１）（Ｎ＋１），因此该算法程序段的频度 厂（Ｎ）一Ｎ／Ｚ十２＊（Ｎ＋１）（Ｎ＋１），该程序段的时间复杂 第１３卷第１Ｏ期 ２Ｏ１４年１Ｏ月 软件导刊 Ｓｏｆｔｗａｒｅ Ｇｕｉｄｅ Ｖ０１．１３ＮＯ．１Ｏ ０ｃｔ．２Ｏ１４ 自定义采煤机滚筒式碰撞体研究与实现 宋园园 ，宋代广。，彭延军 （１．山东科技大学信息科学与工程学院，山东青岛２６６５９０； ２．临矿集团临沂亿金物资有限责任公司，山东临沂２７６０１６） 摘 要：在交互式仿真环境下，采煤机削采煤炭的核心技术就是一个不规则几何体对另一个不规则几何体的碰撞检 测问题。为了使采煤机和煤块之间的碰撞效果更逼真，定义了一种面向采煤机滚筒的自定义碰撞体，并将其作为自 定义插件应用到Ｕｎｉｔｙ环境下。 关键词：不规则几何体；碰撞检测；自定义碰撞体 ＤＯＩ：１０．１１９０７／ｒｊｄｋ．１４３３２８ 中图分类号：ＴＰ３１２ 文献标识码：Ａ 文章编号：１６７２－７８００（２０１４）０１０—００５８—０３ 方向包围盒，离散方向多面体包围盒的方法 ］。但这些 ０ 引言 三维场景下的物体形状大多是不规则的、复杂的，物 体间碰撞检测的实现困难、耗时，碰撞检测的实时性和准 确性尤为重要。 方法很难同时实现碰撞的实时性和精确性。 Ｕｎｉｔｙ ３Ｄ交互式仿真工具提供了球体包围盒、立体 包围盒、胶囊包围盒、面包围盒４种包围盒碰撞检测模型。 使用这４种包围盒的原则是尽可能地使得碰撞模型最大 限度地充满包围盒。球体包围盒适用于类球形，立体包围 盒适用于有棱角的凹凸多面体，胶囊包围盒适用于圆滑的 类椭球形体，也可与其它包围盒结合使用，面包围盒则适 用于不规则的碰撞体。 目前，国内外的碰撞检测算法有层次包围盒方法、时 空包围盒法、距离跟踪法、空间分解法等多种，其中应用最 广泛的是层次包围盒方法，包括球体包围盒、轴向包围盒、 度也为Ｔ（ｎ）一Ｏ（ｎ ）。 ３．３算法执行时间效率测试 算法和坐标求值求解算法的空间复杂度一样，两种算法的 执行时间效率也基本一致。虽然螺旋矩阵的问题早已解 决，但相同的问题可以用不同算法来解决，因为算法的质量 优劣将直接影响到算法乃至程序的执行效率。算法分析的 目的是选择合适的算法和改进算法，以最优方法解决问题， 算法执行时间效率是依据该算法编制的程序在计算 机上运行时所消耗的时间来度量。通常度量一个程序的 执行时间有两种方法：事前分析估算的方法和事后统计的 方法，而算法的时间复杂度研究正是对算法的事前分析估 算。于是将两种算法置于ＶＣ６．０的测试环境中，通过改 变Ｎ的大小，得到两个算法消耗的时间量，如表１所示。 表１算法时间耗费统计 算法１时间量算法２时间量０ ０ ０ ０ ３１ ３１ １５６ １５６ ６５５ ６２４ １ ８４０ １ ６８４ 因此在螺旋矩阵问题上还需研究者探寻更优的算法。 参考文献： ［１］潘大志，张世禄．螺旋矩阵算法设计与实现［Ｊ］．电脑开发与应用， ２００７，２０（６）：４０－４１． （单位：ｍｓ） ６ １４６ ６ １１５ ２２ ９３２ ２２ ９００ Ｎ一４ Ｎ＝８ Ｎ＝１６ Ｎ一３２ Ｎ＝６４ Ｎ＝１２８ Ｎ＝２５６ Ｎ＝５００ ［２］严蔚敏，吴伟民．数据结构：Ｃ语言版［Ｍ］．北京：北京清华大学出版 社，２００７． ［３］ ［美］ＣＯＲＭＥＮ Ｔ Ｈ．算法导论［Ｍ］．殷建平，译．北京：机械工业出 ４ 结语 通过以上分析与测试，按旋转方向构建螺旋矩阵求解 基金项目：国家８６３课题（２０１２ＡＡ０６２２０２） 版社，２Ｏ１３． （责任编辑：孙娟） 作者简介：宋园园（１９９０－－），女，山东聊城人，山东科技大学信，ｇＮｕＳ与工程学院硕士研究生，研究方向为多媒体技术；宋代广（１９７８－－）， 男，山东临沂人，临矿集团临沂亿金物资有限责任公司科长，研究方向为信息管理；彭延军（１９７１一），男，山东青岛人，博士，山 东科技大学信息科学与工程学院教授，研究方向为计算机体系结构、科学计算可视化。