据说是电脑报上的一道题:给一个方阵从外层向内层逐一编号,结果如下所示:(8*8方阵)
1 28 27 26 25 24 23 22
2 29 48 47 46 45 44 21
3 30 49 60 59 58 43 20
4 31 50 61 64 57 42 19
5 32 51 62 63 56 41 18
6 33 52 53 54 55 40 17
7 34 35 36 37 38 39 16
8 9 10 11 12 13 14 15
我试着用递归实现,然后将之转换成非递归实现.可能不说最精,但希望抛砖引玉,能看到更精妙的实现方式!
递归算法:
/* By zzmdl,2005-4-6 */
#define N 8 /* 定义方阵的大小 */
void print_array(int,int array[][]);
void draw(int,int,int array[][]);
main()
{
int i,j,array[N][N];
draw(N,0,1,array);
print_array(N,array);
}
void print_array(int n,int array[N][N])
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d\t",array[i][j];
printf("\n");
}
printf("\n");
}
void draw(int n,int level,int k,int array[N][N])
{
int a;
if(level>N/2) return; /*level用以记录正在给方阵第层进行编号*/
else{
for(a=level;a<N-level;a++)
{array[a][level]=k;k++;} /*编左边; */
for(a=level+1;a<N-level;a++)
{array[N-level-1][a]=k;k++;}/*编下边; */
for(a=N-2-level;a>=level;a--)
{array[a][N-level-1]=k;k++;}/*编右边; */
for(a=N-2-level;a>=level+1;a--)/*编上边; */
{array[level][a]=k;k++;}
draw(n,level+1,k,array); /*递归调用 */
}
}
非递归算法:
/* By zzmdl,2005-4-6 */
#define N 8
void print_array(int,int array[][]);
void draw(int,int array[][]);
main()
{
int i,j,array[N][N];
draw(1,array);
print_array(N,array);
}
void print_array(int n,int array[N][N])
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d\t",array[i][j]);
printf("\n");
}
printf("\n");
}
void draw(int k,int array[N][N])
{
int a;
int level=0;
while(level<=N/2)
{
for(a=level;a<N-level;a++)
{array[a][level]=k;k++;}
for(a=level+1;a<N-level;a++)
{array[N-level-1][a]=k;k++;}
for(a=N-2-level;a>=level;a--)
{array[a][N-level-1]=k;k++;}
for(a=N-2-level;a>=level+1;a--)
{array[level][a]=k;k++;}
level++;
}
}
续:从上面两种实现方式可以看出,递归算法易理解和实现,但可以测试发现,速度要慢于非递归算法.
不过,我今天做了一个实验,发现两者的速度是一样的,不知是什么问题,正在处理!