一个有关问题的探讨

一个问题的探讨
原帖是http://topic.csdn.net/u/20110428/13/cbb92dc2-0005-42ba-9130-966784b041a4_2.html
因为连续发了三个贴，自己感觉有些没说清 在这里补充


输入一个数字N， 输出N的顺时针螺旋递增矩阵，
如输入N=6
应该输出
1 2 3 4 5 6 
20 21 22 23 24 7 
19 32 33 34 25 8 
18 31 36 35 26 9 
17 30 29 28 27 10 
16 15 14 13 12 11 


尽量精简的代码呵呵
要点是
f(a,b,N) :
  a==1 答案是 b
  b==1||b==N||a==N时 答案是b+(N-1)*旋转次数 把(a,b)旋转到a=1的情况 每次旋转时 (a,b)=>(N-b+1,a) 走过了N-1的长度
  其他情况 f(a-1,b-1,N-2)+(N-1)*4 也就是剥去最外面整环(N-1)*4的'小一圈'的情况
   
时间复杂度O(N^3)空间复杂度O(N)

C/C++ code

#include "cstdio"  // stdio.h#include "cstdlib" // stdlib.hint r(int a, int b, int N){    return a==1? b : (b==1 || b==N || a==N) ? r(N-b+1,a,N)+N-1 : r(a-1,b-1,N-2)+(N-1)*4;}int main(){        const int N = 10; //scanf("%d", &N);        for (int i=1; i<=N; i++, printf("\n"))            for (int j=1; j<=N; j++)            {                    printf("%d ", r(i, j, N));            }           return 0;}

C/C++ code

#include "cstdio"  // stdio.h#include "cstdlib" // stdlib.hint main(){        //scanf("%d", &N);        const int N = 8;        for (int i=1; i<=N; i++, printf("\n"))            for (int j=1; j<=N; j++)            {                    int a=i, b=j;                    int z[] = {a-1, b-1, N-a, N-b};                    int reduce = N+1;                    for (int k=0; k<4; k++) if (z[k] < reduce) reduce = z[k];                    int ring     = N - reduce*2;                       // = a,b is at a ring with size = ring                    int ans     = (N * reduce - reduce * reduce) * 4; // = (N-1)*4 + (N-3)*4 + ... (ring-1) * 4                    int quaring    = (ring - 1);                        // = 1/4 perimeter of ring                    int t;                    a-=reduce, b-=reduce;                    while (a != 1) { ans += quaring; t=a; a=ring-b+1; b=t;} // rotate until a = 1                    printf("%d ", ans+b);            }                        return 0;}