前言
全國青少年信息學(xué)（計(jì)算機(jī)）奧林匹克競賽常常要用到許多經(jīng)典算法,比如約瑟夫問題、螺旋方陣、漢諾塔、八皇后問題等,而 螺旋方陣問題是其中較為常用的一種。這類問題的算法分析對于計(jì)算機(jī)圖形學(xué)、解析幾何中的相關(guān)問題都有一定的啟發(fā)性。盡管現(xiàn)有算法已取得了令人振奮的成績， 但依然具有一定的片面性，或者說過于復(fù)雜。實(shí)際上，這個問題有不同的解決算法，鑒于這個問題具有一定的典型性，本文針對信息學(xué)奧林匹克競賽這一問題進(jìn)行了 全面系統(tǒng)的分析、歸納，從不同的角度對這個問題的算法進(jìn)行分析并通過程序?qū)崿F(xiàn)。使讀者對這個問題在算法選擇上有更大的余地，從而避免算法的單一性，同時(shí)對 于類似相關(guān)問題的解決也有一定的啟發(fā)和幫助。
2 問題的描述與分析
關(guān)于螺旋方陣的輸出主要是指將一些數(shù)據(jù)或符號按照一定的順序輸出到計(jì)算機(jī)的屏幕上或者是輸出到一個指定的文件中去,輸出的幾種常見情況如下圖(為簡單起見,以輸出5階的數(shù)字螺旋方陣為例):
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
4 19 20 21 10
5 6 7 8 9
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
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
圖1由外及里順時(shí)針；圖2由外及里逆時(shí)針；圖3由里及外順時(shí)針；圖4由里及外逆時(shí)針
在實(shí)際應(yīng)用中,輸出的內(nèi)容可以不盡相同。在上面的圖1至圖4中，按螺旋順序輸出的數(shù)顯然有一定的規(guī)律，而實(shí)際輸出的順序往往不是按照螺旋順序，通常是將上圖中的數(shù)據(jù)按行（或按列）輸出，因此這類問題的關(guān)鍵在于如何將有規(guī)律的數(shù)據(jù)與實(shí)際輸出時(shí)的先后順序?qū)?yīng)起來。下面采用不同的算法來實(shí)現(xiàn)。
3 采用不同算法解決螺旋方陣的輸出
3．1非遞歸算法
3.1.1 “海龜”算法（順時(shí)針，由外及里）
參照海龜行走的做法，用一對變量A，B模擬海龜頭的方向，根據(jù)屏幕坐標(biāo)的特點(diǎn)，A、B的取值和“海龜頭”方向有這樣的關(guān)系：(0,1)表示向右；(0, -1)表示向左；(-1,0)表示向上；(1,0)表示向下；用另一對變量X，Y模擬海龜位置，“海龜”每前進(jìn)一步，它的新位置即為X=X+A，Y=Y+B；要海龜向右轉(zhuǎn)，就改變A、B的值，根據(jù)數(shù)學(xué)知識可以得出具體的變換公式是：C=A；A=B；B=-C。下面用自然語言對算法進(jìn)行描述：讓海龜先走n步，然后右轉(zhuǎn)，再走n-1步，再右轉(zhuǎn)，再走n-1步，再右轉(zhuǎn)，再走n-2步，再右轉(zhuǎn)，再走n-2步……如此類推，直到海龜前進(jìn)的步數(shù)為0時(shí)停止；而每當(dāng)“海龜”前進(jìn)1步，就在它位置上顯示一個數(shù)字，那么前進(jìn)n步即重復(fù)執(zhí)行“X：=X+A，Y：=Y+B”語句n次。但如何讓下兩個循環(huán)的重復(fù)次數(shù)都為n-1呢？解決的方法是：循環(huán)n次后，讓n的值減少0.5，然后再轉(zhuǎn)回執(zhí)行同樣的循環(huán)。擴(kuò)展到顯示n位數(shù)，則須留n列的位置，也就是說，海龜水平方向每次得前進(jìn)n步，才有足夠的位置顯示大一點(diǎn)的數(shù)字方陣，需把Y=Y+B改成Y=Y+n*B就行了。“海龜”算法的優(yōu)點(diǎn)是簡潔清晰。
3.1.2 “分割”算法（逆時(shí)針，由外及里）
設(shè)螺旋方陣對應(yīng)的一般二維數(shù)組如下：
a00 a01 a02 a03 a04
a10 a11 a12 a13 a14
a20 a21 a22 a23 a24
a30 a31 a32 a33 a34
a40 a41 a42 a43 a44
圖5
按逆時(shí)針方向從外向內(nèi)，一層層給下標(biāo)變量賦值，由于階數(shù)n的任意性，需考慮以下幾個問題：層數(shù)k與階數(shù)n的關(guān)系式，n由用戶輸入，k根據(jù)n來計(jì)算；定義變量value,賦值時(shí)讓其自增；分析每層矩形四條邊元素的下標(biāo)變化規(guī)律，將方陣元素按逆時(shí)針方向分成四個部分：方陣左半邊（三列），方陣下半邊（二行），方陣右半邊（兩列），方陣上半邊（二行）。
具體算法思想：以5階方陣為例，可判斷 k=[(n+1)/2]=3,用循環(huán)控制產(chǎn)生的層數(shù)，語句為for(k=0,k <(n+1)/2;k++)。
Step1：找出方陣左半邊列規(guī)律：列下標(biāo)正好是層數(shù)k的值，行下標(biāo)在第一列從0變到4，第二列從1變到3，在第三列從2變到2，故推導(dǎo)出n階螺旋方陣左半邊由外到內(nèi)的列循環(huán)結(jié)構(gòu)：for(i=k；i <n-k；i++) mat[i][k]=value++;此循環(huán)執(zhí)行一次，產(chǎn)生一列元素，循環(huán)執(zhí)行的次數(shù)由外循環(huán)來控制。
Step2：找出方陣下半邊行規(guī)律：行下標(biāo)從４變到３，每層取值為n―k―1；列下標(biāo)由外到內(nèi)第一行從１變到4（a40已產(chǎn)生），第二行（a30 、a31已產(chǎn)生）從２變到3，第三行只有一個元素a22，故推導(dǎo)出n階螺旋方陣下半邊行循環(huán)結(jié)構(gòu)：for(i=k+1；i <n-k；i++) mat[n-k-1][i]=value++;
Step3：找出方陣右半邊列規(guī)律：行下標(biāo)第一列從3變化到０（a44已產(chǎn)生），第二列從２變到１（a43、a33、a03已產(chǎn)生），可推斷行的初值為n-k-2;列下標(biāo)沒變化，兩列的下標(biāo)分別為４、３，故推斷出右半邊的列可由下列循環(huán)結(jié)構(gòu)完成：for(i=n-k-2；i >=k；i--) mat[i][n-k-1]=value++;
Step4：找出方陣上半邊行規(guī)律：已經(jīng)產(chǎn)生了的元素不能再重新賦值，而行下標(biāo)可用層次k來表示，列下標(biāo)與右半邊行下標(biāo)變化規(guī)律一樣，由此推斷出上半邊的行可由下列循環(huán)結(jié)構(gòu)完成：for(i=n-k-2；i >k；i--) mat[k][i]=value++。
當(dāng)k取一個值時(shí)，以上四個循環(huán)依序各產(chǎn)生一列或一行元素，由此產(chǎn)生一層元素，當(dāng)k在變化范圍［０…(n+1)/2］內(nèi)依次取值時(shí)，四個循環(huán)輪流執(zhí)行，一個數(shù)字螺旋方陣就這樣生成了。
3．2 遞歸算法
分析圖五容易看出，當(dāng)由外及里順時(shí)針旋轉(zhuǎn)時(shí)，最外層數(shù)據(jù)輸出后，內(nèi)層的圖形只不過是層數(shù)減少了，即問題的規(guī)模變小了，但問題的性質(zhì)沒有發(fā)生變化，新問題和原問題仍然可以采用相同的解法。所以這一問題完全可以采用遞歸的方法來求解。具體的算法描述如下。
Step1：初始化。把需要輸出的數(shù)據(jù)放入一維數(shù)組，設(shè)為b[1..n*n]。因?yàn)槭莕階方陣，所以全部元素共有n2個，輸出b[1]到b[n*n]的順序是方陣順時(shí)針旋轉(zhuǎn)的順序。
Step2：把b數(shù)組中的每個元素放入到二維數(shù)組a[i][j]（圖5）中去，如b[1]放入a[0][0]中，b[2]放入a[0][1]中，……，b[6]放入a[1][4]中……，其它元素依次放入。
Step3：按行輸出數(shù)組元素a[i][j]即可。
上述算法中，難點(diǎn)在于如何將b數(shù)組放入到a[i][j]數(shù)組對應(yīng)的分量中去。為此，對step2進(jìn)行求精并使用遞歸來解決。具體做法：將數(shù)組a初始化為0。設(shè)置變量direction作為方向標(biāo)志。當(dāng)direction為1、2、3、4時(shí)，分別表示向右、向下、向左、向上。并編寫如下的遞歸子程序walk(x,y,direction,k)。其中參數(shù)x,y表示數(shù)組的下標(biāo)。k是計(jì)數(shù)器。當(dāng) k>n*n 為遞歸出口。
case direction of
{right } 1： if到右邊界then 向下拐 else 向右輸出；
{down} 2： if到下邊界 then 向左拐 else 向下輸出；
{left} 3： if到左邊界 then 向上拐 else 向左輸出；
{up} 4： if 到上邊界 then 向右拐 else 向上輸出。
end;{end case}
3．3 算法實(shí)現(xiàn)
限于篇幅，本文僅給出遞歸算法的主要程序段（pascal語言）
procedure walk(x,y,direction,k:integer);
begin
if k>n*n then 按行輸出a數(shù)組；
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);
{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 結(jié)束語
關(guān)于螺旋方陣的輸出算法主要有上述幾種，其他幾種方陣的輸出，可以仿照上述的算法分析加以實(shí)現(xiàn)。相對而言,遞 歸算法較為簡潔，但是時(shí)間復(fù)雜度要高一些，對于輸出高階螺旋方陣時(shí)，時(shí)間很長。另外在空間復(fù)雜度方面，采用數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，顯然有一定的局限性，如果使 用鏈表來存儲，將會盡可能地避免空間不足的現(xiàn)象。另外，上述問題也可以使用一個模板式的子程序來完成，這時(shí)要求輸入的參數(shù)要包括：從外還是從里螺旋、順時(shí) 針還是逆時(shí)針，起點(diǎn)坐標(biāo)等參數(shù)，對于從里向外螺旋時(shí)，還要考慮螺旋方陣的階數(shù)是奇數(shù)還是偶數(shù)，分別給予不同的處理。
本篇文章來源于 義烏信息技術(shù)教研網(wǎng) 原文鏈接：http://www.ywhs.net/itedu/html/aosaifudao/mingshifudao/20071125/47.html