n阶螺旋方阵的算法分析.pdf

1996年12月第1 3 卷第4期广西 师 院学报(自然科学版)Jo ur nalof Gu angxiTe aehersCol le罗(NaturalS cieneeE ditio n)I戈e.1996Vo】.13,No.4n阶螺旋方阵的生成彭月英(广西师 范学院 计算 中心,南 宁,5300 01)摘典该文使用C语 言编 程,实现了对 任意自然数n的n阶螺 旋 方阵的自动生成及打印。关扭词,阶 方阵;”阶螺旋方阵;二维数纽,循环;N一S图1引言与间题所谓n阶螺旋方阵是指形如.巨fe ee二OJ,立由外向内一层 一层生成的n阶方阵(此处n一7)。这类方阵在现代物理、计算方法及计算机图形学等学科中有着十分重 要的应用。因此我们来讨论它的生成问题。一般方阵的打印在程序设计中是先定义 一个二维数组,然后对此数组 人为地初始化或 逐个赋值,一个程序只能产生 一个或固定几个具体的方阵。例如,对 干以下的5阶螺施方阵9口八乙,1,.1吐占OJ11今自JJL L人,.19曰卜以口矛111.11乙八1 11()92 2肘8朴2 07l8l,56方阵可用 如 下初 始化 方法给 二维 数组 元素赋值兀收稿日期:19 96一08一29广西 师 院学报(自然科学版)第1 3卷inta5 5=1,1 6,15,14,13,2,17,24,23,12,3,18,25,22,1 1,4,19,20,21,10,5,6,7,8,9;然后用如下语句进行打印for(i=0;i5;i+)for(jo;j(5;j+)printf(“%4d,ai j);prin tf(“/n,);printf(“/n,);方 阵1即可得到打印输出。而这样设计的程序没有通用性。只能打印这一个5阶螺旋方阵。若要打印6阶螺旋方阵,又要重新定义数组,且重新初始化.即人先要在纸上书写出这个6阶方阵,才能把数据写入程序中。当阶数很大时,工作量相当大。本文是想寻求使用一个程序,就能打印出用户需要的任何阶数的螺旋方阵,并且方阵的.元素值全部由程序根据阶数自动产生。为此,我们以5阶螺旋方阵为例,详细分析了该方阵的特点,总结推导出生成n阶螺旋方阵的一般规律。由此写出程序,每次运行时只要用户给出一个n的具体数值,该程序就能 自动生成一个对应的螺旋方阵。假设n5,则5阶螺方阵应按箭头方向如下生成OdO乙1 1刁.上甲自.l月队O口工,IC了,.占一乃夕l丹匕甲t,.几一.几1 110勺乙119n乙28251 9206789,l乃nJJL L人尸O.叮.山方阵2此方阵对应的一般二维数组方阵设计如下J马孟,曰,La a口02口o a己1 2口la.月弓,da a.,J月.J,目,da a,目,da a气上,.L.,山a a如果要按箭头所示方向从外向内,要考虑如下三个间题:口4 1口42口毛3口4-方阵3一层 一层给下标变量赋值,考虑到阶数n的任意性,故nU0nJC0,1几,J月,a a a a a.1.e sl月月e s.几.几w e人甘(l)要找出层数k与阶数n的关系式,假定n由用 户输入,k要在 程序中根据n计算出来。(2)定义变量value=1,然后赋值时让它v alue+;第4期彭月英:,阶螺旋方阵的生成(3)要找出生成每层四条边的元素的下标变化的规律。为了解决这些间题,我们把方阵拆开来看,把方阵3的元素按箭头方向分成如下四个部分:、1)方阵左半边:垂直向下的三个箭头所示 的三列元素;(2)方阵下半边:从左向右的水平箭头所示的两行元素;(3)方阵右半边:从下到上的竖箭头所示的两列元素;(4)方阵上半边:从右到左的水平箭头所示的两行元素。下面我们通过讨论如何给这四部分的元素赋值,来解决n阶螺旋方阵的赋值问题。2算法推出与程序设计假定n阶螺旋方阵有k层,每层由四边组成,则由方阵3看,层数k从。开始,先产生第o层,再产生第一层,然后产生第二层。5阶方阵只有3层,35+12,由此可推出n阶螺旋方阵有 华层,*从。开始,故kn+l2,由此想到设计一个外循环来控制产生的层数:for(k=0;k(n+l)/2;k+)下面我们来看看方阵3左半边的列的元素(不妨设为a l)从外到 内下标变化的规律:列下标S正好是层数k的值,它在产生一列元素时不变。行下标l在产生第一列时,从。变到4,在产生第二列时,从l变到3,在产生第三列时从2变到2,故推导出产生n阶螺旋方阵左半边由外到内的列的循环结构为for(i=k;in一k;i+)matik=v目ue+;这个循环结构被执行一轮,产生一列元素,可由外循环k来控制它将被执行多少轮。方阵3下半边的行的元素a l s,从外到内下标变化的规律如下:行下标l从4变到3,对应每一层的值为n一k一1,它在产生一行的元素时不变,而列下标:在产生倒数第一行时第一个元素不算)从1开始变到4;在产生倒数第二行时(第一、第二个元素不算)从2开始变到3,第3层只有一个元素兔:,已由前一个循环结构产生,故推 出产生方阵下半边由外到 内的行的循环结构为f or(ik+l;i(n一k;i+)matn一k一1i=v alu e+;我们再考虑如下发现:h2时,是第3层,从方阵2中看,第三层 的元素自2已由左半边列的循环产生。此时,进入此循环时,i3,又要先判断i5一2,即ik,i这时为1,即12,条件为假,赋值语句不再被执行,所以,n一k一1只能被广西师 院 学报(自然科学版)第 1 3卷执行两次,即等于4和3的两次。由此推出右半边的每一列的产 生可由下 列循环结构 完成for(i=n一k一2;i=k;i一一)mati n一k一l=valu e+;方 阵3上半边的行,每行的元素是从右到左产生的,当然,已经螺旋产 生 了的元素就不再重新赋值。所以,第一行是要依次产生a 03,a 0:,a 01,第二行只须给a lZ赋值就可以了。如此推出,行下标可用 层数k来表示。列下标的变化,第一行是从3变到1,与右半边的行下标变化规律一致,由此推出给方阵上半边的元素赋值的循环结构为f or(i一粉一k一2;泛k,i一一)mat走iv alue+;当k取一个值时,以上四个循环 依序各产生一 列或一行的元素。由此而产生一层的元素,二。工_、,一一一一,.一二_n+l、一一、,、*.L一二,一一._,_一、_那么,当k在它的变化 范 围0.二生一)的依次取各值一 遍时,四个循环轮流执行。螺旋方阵一,一一-一”甲一“一一2护、,、一曰一刁一“R一”“t,I“护“刁.用、刀丁的赋值就全部完成了。接下来的工作那是把已赋好值的二组数组按方阵的形式打印出来即可。而这用一个二重循环即可完成,以下是 上机程序。#defineL50#inelude“stdio.h,main()inti,j,k,n;intmatIJL,valu e一1;printf(”ple a s einPutdime n sio nofmarn即);prin tf(”n=?,);s e ant(”%d,.己.n);for(k=0;k(n+1)/2;k+)for(i一k;i灯n一k;i+)matik=valu e十一斗一;for(i一k+l;i=k;i一一)matin一k一l一v alu e+;拓r(i 一n一k一 2;l夕k;l-一)matki=value+;丁 r Intf(、n,);f()r(一=();i了n;i一书+)for(j=0;jn,j一干+)printf(,%4d“,mati 仁jl);printf(”、n,);printf(”n,);第4期彭 月英:n阶螺旋方阵的生成3程序的N一S图输输 人n阶方阵的n值值k k k=0 0 0k k k(n十l)/2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2二二i=k k ki i i i in一k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k漂漂漂毕坦一一一kj=v alue+i i i i i i i+i i i i i=k+1 1 1i i i i ik k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k呼呼呼婴些卫逊丝兰一一1一v alu e+1 1 1 1 1 1 1 i i i i i=n一k一2 2 2i i i i ik k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k津津津毛界里二一二v alue+1 1 1 1 1 1 1k k k k k+十十打打印机换行行i i i=0 0 0i i i i i i in n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n俞俞垂亩二0 0j j j j jn n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n 打印mat口的值(占4个字符)换换换行,打一空行行i i i i i+4运行程序实例2。阶螺旋方 阵的生成Ple a s einPutdim ensio nofmatn一?20八6门Jl八bl匀乙八jg自2OQ“8tl叹dto匕刁广O成J工以dl口尸匀LOA人月住注才7 57473727 1706 9686766656 4636261605914 414 31421411 生 01 3 91 3813 71 3 613 51 341 3 31 3213 11301291281 4 52042032022012001991981 9 719 61951 941 9 31 921 9 11 901 2714 620 52562 5525 425 32522 5 12502492482 4724 62452441 891 261472()625 730 02 9929829 729 629 52 942 9 329229 129024318 81 251482()725 83013363 3 53 343 333 323 313 303293 2 82 892421871241 4 920825 93023373 6 43633623 6 13 603593583272 8 824 11861231 5()2092603033 383 653 843 8 33 8 23 8 13803573 2 62 8724018512 215121026 13043393663 853 963 953 9 43 7 935632528623 918 41211 5221 126 230 53403 673 8 63 9 74()03 9 337835 532428523 818312()1532 122633063 413 683 873 9 839939 237 735 432 32 8423 71821 1 915421326 43073423 6 93 883893903 9 137 63 5 33222832 361811188 0 7 8 7 9 7 78 18 7 8 6 8 5 8 3 8 4 8 224 35670 0 91 01 11 2广西师院学报(自然科学版)第 1 3卷15 521 42 65308343一3703 713723733743753 523212 8 22 351801 1 74 615 62 152 663093 4 43 4 5,3 4634734834 935 035132028123 41791164 51572 162 673 1031 13123133143153 1631731831928023 31781154 41 5821 72682692702 7 127227327 427527627727827 923 217 71 14431 5 92182192 2022 12222232242252 2 622722822923023 11 7 61 1 34 216 01611 621 6 31641 6 516 61671 681 6 91 701 7 117217317 41 7 51 1241959697989 910 010110210310410 510610710810911011 140222324252 62728293031323 3343536373839吕OJ01.上,自八d吐,.占八6八匕OJO甘O甘O甘O甘O心。口左占口 成七780011111111,11.11上n乙参考文献 l 谭浩强等.C语言程序设计教程.北京:高等教育 出版社,1 992 z 尤晋元等.C语言程序设计.上海:上海科学技术 文献出版社,1987 习徐君毅等.实用C语言.上海:复且大学出版社,198 7 4 【美He rb叮t反hil dt著;郭兴社等译.C语言大全.北京:电子工业出版社出版,1 99。5朱洪等.算法设计和分析.上海:上海科学技术文献出版社,19896 美J am e:D.Foley.Andr ie sv anDam著;唐译圣等译.交互式计算机 图形学基础.北京:清华大学出版社,1 986Genratf ono fn一th一OrderTorsio nSqu areMatrix尸翻gy 旅洲z,(C omputerCentr e,GuangxiTea eher sC ollege,Nan ning,5 3 0 001)A bs tr ac t:Thispaperde signsaprogr amwit hC language.Itr ealiz e sa utomatiegene r ationa ndPrin tKeyofn一th一 orde rto r sion钩ua r ematrixWO rdSsion ala r r ay;lo oP;n一th一orde rsqua rematrix;n一th一orderto rsionsqua r ematrix;two一dimen-N一5graph