n阶螺旋阵问题求解

【问题描述】创建n阶螺旋矩阵并输出。

输入描述：输入包含多个测试用例，每个测试用例为一行，包含一个正整数n(1<=n<=50)，以输入0表示结束。

输出描述：每个测试用例输出n行，每行包括n个整数，整数之间用一个空格分割。

输入样例：

4

0

样例输出：

   1  2  3  4

12 13 14 5

11 16 15 6

10   9   8 7

【思路】因为这是递归算法设计这一章的内容，所以我们要朝着递归的思路去想（最开始我想用循环来实现，发现非常麻烦=_=）。经过分析，发现这个n阶阵可以分成不同层的方阵进行填充，并且填充的数是连续的，可以分解为多个层来进行递归求解，如图：

对于每一层，均从左上角起始元素开始填充，直到填充完四条边到起始元素下方截止，进行下一层的填充，调用自身进行递归；

对此，定义一个printImage函数进行求解；

printImage中需要传入3个变量；1）该层起始元素的值 int s；2）该层方阵的边长（阶数）int n；3）该层的层数 int k，即当前是第几个螺旋阵；

代码如下：

#include<stdio.h>

int n;
int a[50][50];
int i,j;
int main()
{

    while(1)
    {
        scanf("%d\n",&n);
        if(n!=0)
        {
            printImage(1,n,1);
            for(i=1; i<=n; i++)
            {
                for(j=1; j<=n; j++)
                {
                    printf("%d ",a[i][j]);
                }

                printf("\n");
            }
        }
    }
    return 0;
}


void printImage(int s,int len,int k)
{
    if(len==1)//递归出口，n为奇数的情况
    {
        a[k][k]=s;
        return;
    }
    else if(len==2)//递归出口，n为偶数的情况
    {
        a[k][k]=s;
        a[k][k+1]=s++;
        a[k+1][k+1]=s++;
        a[k+1][k]=s++;

        return;
    }

    int col=n+1-k;//此处定义最右侧和最下侧列的数组所在位置
    int x=s;
    for(j=k; j<=col; j++)//此处构造第k层的上部分，j和层数有关
    {
        a[k][j]=x;
        x++;
    }

    for(i=k+1; i<=col; i++)//构造第k层的右侧部分；
    {
        a[i][col]=x;
        x++;
    }

    for(j=col-1; j>=k; j--)//构造下侧部分
    {
        a[col][j]=x;
        x++;
    }

    for(i=col-1; i>=k+1; i--)//构造左侧部分，注意条件是k+1不要重复给起始位置元素赋值
    {
        a[i][k]=x;
        x++;
    }

    printImage(x,len-2,k+1);//进行创建下一层的螺旋阵

}

输入输出样例：

总结：递归类问题需要将一个大问题分解为小问题，直至找到递归出口为止。