### 問題描述 螺旋矩陣是一個nxn的方陣，其中元素為自然數，但像螺旋方向一樣遞增。舉例如下： 若n = 3，螺旋矩陣為： ~~~ 1 2 3 8 9 4 7 6 5 ~~~ 若n = 4，螺旋矩陣為： ~~~ 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 ~~~ ~~~ 若n = 5，螺旋矩陣是： ~~~ ~~~ 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 ~~~ 那么如何打印這樣的矩陣呢？ ### 解析 當然它的規律很簡單，直接的方法就是先申請一個矩陣，然后按螺旋方向填入相應的元素，填充完畢后再打印出來。它的時間按復雜為O(n2)，已經是最優的（為什么？）。空間復雜度也為O(n2）。似乎已經很好了。 但是還不夠好。 按照矩陣規律填充元素時，我們是隨機訪問矩陣元素的（如果可以按順序訪問，根本不用先存起來再打印）。隨機訪問內存，效率當然不高。所以即使時間復雜度已為最優，但那只是理論上的最優，在實踐中表現并不一定就好。 假如能根據行列號直接計算出對應的矩陣元素就好了。當n給定后，這個矩陣就已經唯一確定了，那么每一個元素也是確定的。也就是說，每一個位置放什么元素僅僅取決于n。因此我們可以找到一個函數*element*(*i, j*)，將行號i和列號j映射成對應這個行列號的元素。當然這個函數肯定不是一個簡單的函數，不是一眼就可以看出來的，但也并不是不可能。 現在我們就來考查一下這個矩陣有什么特點。注意觀察一下螺旋矩陣的最外層，它的左上角的元素是最小的，然后沿順時針方向遞增，就如同一個環一樣（比如n為4時，1, 2, ..., 12就是最外面一層環）。再注意一下里面一層，也是一樣，順時針方向遞增的一個環（比如n為4時，13, 14, 15, 16就是里面一層環）。以此類推，環里面還有一層環（n為4時有2層環，n為5時有3層環，最里面一層只有一個元素25），實際上是一個圓環套圓環結構。每一圓環最關鍵的元素就是左上角的那一個元素。只要知道了這個元素，再加上這個正方形環的邊長就可以計算出剩下的元素。設左上角元素為a，邊長為l（ell），也就是邊上有幾個元素，并假設左上角的行號和列號均為0，其它元素的行號和列號都以它作參考，計算方法如下所示： 1. 若i == 0，*element*(*i, j*) = a + j; 2. 否則若j == 0，*element*(*i, j*) = a + 4(l-4) - (i-1) - 1; 3. 否則若i == l-1，*element*(*i, j*) = a + 4(l-4) - (l-2) - 1 - j; 4. 否則*element*(*i, j*) = a + l - 1 + i; ### 螺旋矩陣代碼： ~~~ //螺旋矩陣 #include<iostream> using namespace std; int a[10][10]; void Fun(int n) { int m=1; int i,j; for(i =0;i<n/2;i++){ for(j=0;j<n-i;j++){ if(a[i][j] ==0) a[i][j] = m++; } for(j=i+1;j<n-i;j++){ if(a[j][n-1-i] ==0) a[j][n-1-i] = m++; } for(j=n-i-1;j>i;j--){ if(a[n-i-1][j] ==0) a[n-i-1][j] = m++; } for(j=n-i-1;j>i;j--){ if(a[j][i] ==0) a[j][i] = m++; } } if(n%2==1) a[n/2][n/2]=m; } int main(void) { int n,i; cout<<"請輸入螺旋矩陣維數： "<< endl; cin>>n; cout<<"顯示螺旋矩陣數值： "<< endl; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ a[i][j]=0; } } Fun(n); for(i=0;i<n;i++){ for( int j=0;j<n;j++){ cout<<a[i][j]<< "\t"; } cout<<endl; } } ~~~ ### 螺旋隊列 問題描述： 設1的坐標是（0，0），x方向向右為正，y方向向下為正，例如，7的坐標為（-1，-1），2的坐標為（1，0）。編程實現輸入任意一點坐標（x，y），輸出所對應的數字. ### 螺旋隊列代碼： ~~~ // 螺旋隊列.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #define max(a,b) ((a)<(b)?(b):(a)) #define abs(a) ((a)>0?(a):-(a)) using namespace std; int foo(int x,int y) { int t = max(abs(x),abs(y)); int u = t+t; int v = u-1; v= v*v+u; if(x == -t) v+=u+t-y; else if(y==-t) v+=3*u+x-t; else if(y ==t) v+= t-x; else v+=y-t; return v; } int _tmain(int argc, _TCHAR* argv[]) { int x ,y; int N; cout<<"請輸入螺旋隊列數字： "<<endl; cin>>N; cout<<"顯示螺旋隊列數值： "<<endl; for(y=-N;y<=N;y++) { for(x=-N;x<=N;x++) cout<<"\t"<<foo(x,y); cout<<endl; } while(scanf("%d%d",&x,&y)==2) //printf("%d\n",foo(x,y)); cout<<"\t"<<foo(x,y); return 0; } ~~~ **轉載請注明出處**：[http://blog.csdn.net/utimes/article/details/8348243](http://blog.csdn.net/utimes/article/details/8348243)