日期:2014-05-18  浏览次数:20819 次

一个问题的探讨
原帖是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.h


int 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;
}



事实上有时间复杂度为O(N^2)而空间复杂度为O(1)的解法 
也就是把计算(N-1)*4+(N-3)*4+...用公式直接算出来
C/C++ code


#include "cstdio"  // stdio.h
#include "cstdlib" // stdlib.h

int 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;
}




------解决方案--------------------
看完顶上,再去看看原帖去。写个C#去。