一个有意思的C程序,给方阵顺序编号

类别:编程语言 点击:0 评论:0 推荐:

据说是电脑报上的一道题:给一个方阵从外层向内层逐一编号,结果如下所示:(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++;
     }
}

续:从上面两种实现方式可以看出,递归算法易理解和实现,但可以测试发现,速度要慢于非递归算法.

不过,我今天做了一个实验,发现两者的速度是一样的,不知是什么问题,正在处理!

本文地址:http://com.8s8s.com/it/it22519.htm