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