求算法

dzho002

想象成一副2维的图(NxN), 我们要从(0,0)开始遍历这副图.
遍历的顺序是:
1) x=x+1, y=y     
2) x=x,   y=y+1,
3) x=x-1, y=y;
4) x=x    y=y-1;
然后回到 (1)

1-->2-->3-->4-->1....直到所有点都走过.
方向的改变条件是, 按当前方向走的话, 下一点出了图的范围或者已经访问过.
(撞到墙了)
按照这种思路写, 会比较清楚. 而且如果改变(1)-(4)的顺序,可以实现不同的效果.

[PHP]
#include "stdio.h"
int main()
{
  int n,i,j,n2,x,y,x1,y1,pos;
  int* array;
  int current_direction_index=0;
  const char search_directions[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
  printf("lease input a positive integer:");
  scanf("%d",&n);
  if(n<=0)
  {
     printf("go to somewhere else to play\n");
     return -1;
  }
  n2=n*n;
  array=(int*)malloc(sizeof(int)*n2);
  memset(array, 0, sizeof(int)*n2);
  x=0;y=0;
  for(i=1;i<=n2;++i)
  {
     pos=x+y*n;
     array[pos]=i;
     //find new x,y for the next number
         j=current_direction_index; //remember current dir
     while(1)
     {
             //first try current direction
             x1=x+search_directions[current_direction_index][0];
             y1=y+search_directions[current_direction_index][1];
             //if current direction OK.
             if(x1>=0 && x1<n && y1>=0 && y1<n && array[x1+y1*n]==0)
             {
                        x=x1;y=y1; break;
                 }
                current_direction_index=(current_direction_index+1)%4;
                if(j==current_direction_index)
                {
                        //something wrong, most likely the search directions are not properly set
                        //set i=n2, so that for loop will exit.
                        i=n2; break;
                }
         }
  }

  //print the array
  for(y=0;y<n;y++)
    for(x=0;x<n;x++)
  {
          pos=x+y*n;
          printf("%d", array[pos]);
          if(x==n-1) printf("\n");//last element in a row
          else printf("\t");
  }
  free(array);
}
[/PHP]

seablue

最初由 landylau 发表
这个算法还是没看懂，等会再仔细看看，有点意思
虽然一看好像很简单，要我编一个还要想半天阿。等会试试

1. 
   
2.    1    2    3    4    5    6    7    8
   
3.    28   29   30   31   32   33   34    9
   
4.    27   48   49   50   51   52   35   10
   
5.    26   47   60   61   62   53   36   11
   
6.    25   46   59   64   63   54   37   12
   
7.    24   45   58   57   56   55   38   13
   
8.    23   44   43   42   41   40   39   14
   
9.    22   21   20   19   18   17   16   15
   

复制代码

看看这个阵形的规律就明白应该怎么做了：
1）n X n 的阵列；
2）要求往里旋转；
3）从9开始作为0圈算起，9到15有7个数，16到22有7个数；23到28有6个数，29到34有6个数；依此类推。。。故设置K变量进行计数，当走过下边或上边后，K＋＋实现打印边长-1之目的；
4）打印的边界条件是最后一个数是为n&#178;，则停止；
5）让光标回到图形下面。
下面是源代码的详细注解：

1. 
   
2. /*Redhat linux 9.0*/
   
3. #include <stdio.h>
   
4. main(void)
   
5. {
   
6.   int i, j, k, n;
   
7. 
   
8.   printf("Please input number: ");
   
9.   scanf("%d",&n);/*输入希望打印的边长*/
   
10. 
    
11. /*用终端控制码清屏，并打印很多回车；以便下面用终端控制码实现光标向左向上移动*/
    
12.   printf("\33[2J\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\33[20A");
    
13. 
    
14.   for (i=1; i <= n; i++) printf("%5d",i);/*先打印出不参加循环的第一个边*/
    
15. 
    
16. /*循环从第二个边开始，向内旋转*/
    
17.   for (k=1, i=n+1;i <= n*n; i++)
    
18.      {
    
19.        for (j=1; j <= (n-k)&&i <= n*n; j++, i++)
    
20.             printf("\33[1B\33[5D%5d",i);/*本循环打印右边*/
    
21.        for (j=1; j <= (n-k)&&i <= n*n; j++, i++)
    
22.             printf("\33[10D%5d",i);/*本循环打印下边*/
    
23.        k++;/*过了下边后，边长应该-1*/
    
24.        for (j=1; j <= (n-k)&&i <= n*n; j++, i++)
    
25.             printf("\33[1A\33[5D%5d",i);/*本循环打印左边*/
    
26.        for (j=1; j <= (n-k)&&i <= n*n; j++, i++)
    
27.             printf("%5d",i);/*本循环打印上边*/
    
28.        k++,i--;/*过了上边后，边长-1；i--修正了一下bug：避免有些值丢失*/
    
29.       }
    
30. 
    
31.   printf("\33[20B");/*打印终端控制码，让光标移动到图形的下面*/
    
32. }
    

复制代码

注：有关终端控制码，参看shell版的精华部分。

liuspider

Only two nested for loops and one if-sentence can do the job: (without any 1- or 2-dimension arrays)

[PHP]#include <stdio.h>

int main() {
  int X, Y, x, y, round, result, n = 8;
  printf("lease input a number: ");
  scanf("%d",&n);
  for(y = 1; y <= n; y++) {
    for(x = 1; x <= n; x++) {
      X = (1 + n - abs(1 + n-2*x))/2;
      Y = (1 + n - abs(1 + n-2*y))/2;
      round = (X < Y ? X : Y) - 1;
      if (x >= y) {
        result = 4*round*(n-round) + x + y -1 - 2*round;
      } else {
        result = 4*(round+1)*(n-round-1) - x - y + 3 + 2*round;
      }
      printf("%5d", result);
    }
    printf("\n");
  }
  return 0;
}[/PHP]

liuspider

output when n = 10

1. 1    2    3    4    5    6    7    8    9   10
2. 36   37   38   39   40   41   42   43   44   11
3. 35   64   65   66   67   68   69   70   45   12
4. 34   63   84   85   86   87   88   71   46   13
5. 33   62   83   96   97   98   89   72   47   14
6. 32   61   82   95  100   99   90   73   48   15
7. 31   60   81   94   93   92   91   74   49   16
8. 30   59   80   79   78   77   76   75   50   17
9. 29   58   57   56   55   54   53   52   51   18
10. 28   27   26   25   24   23   22   21   20   19

复制代码

starwar

值得学习

yanite

如果不用终端控制码怎么做啊？我在面试时也见到过不过是在win32+c#或Java里面，要一次性打出来啊？

liuspider

the solution I gave out does not require any console formating code

earth

好久没有编程了,看到这个帖子后想练习一下编程,我的思路和dzho002兄相同,在这里复习一下链表和递归调用。

1-->2-->3-->4-->1....直到所有点都走过.
方向的改变条件是, 按当前方向走的话, 下一点出了图的范围或者已经访问过.
(撞到墙了)
按照这种思路写, 会比较清楚. 而且如果改变(1)-(4)的顺序,可以实现不同的效果.

1. #include<stdio.h>
2. #define MAX_ROW 16
3. struct direction
4. {
5.         int dx;
6.         int dy;
7.         char name[5];
8.         struct direction * next;
9. };
10. int main(void)
11. {       
12.         int data[MAX_ROW+2][MAX_ROW+2]={0};
13.         int i=0,j=1,num=0;
14.         struct direction d[4]={{0,1,"Right",},{1,0,"Down",},{0,-1,"Left",},{-1,0,"Up",}};
15.         d[0].next=&d[1];
16.         d[1].next=&d[2];
17.         d[2].next=&d[3];
18.         d[3].next=&d[0];
19.         struct direction * direction=&d[0];
20.         printf("Please enter a integer(not greater than %d)\n",MAX_ROW);
21.         scanf("%d",&num);
22.         if(num>MAX_ROW) exit(2);
23.         data[num+1][num]=1;
24.         data[num][0]=1;
25.         data[1][num+1]=1;
26.         findway(direction,1,0,data);
27.         for(i=1;i<=num;i++){
28.                 for(j=1;j<num;j++) printf("%4d",data[i][j]);
29.                 printf("\n");
30.         }
31.         return 0;
32. }
33. void findway(struct direction * d,int x,int y,int data[MAX_ROW+2][MAX_ROW+2])
34. {       
35.         static int i=1;       
36.         if (data[x+d->dx][y+d->dy]==0){
37.         }
38.         else{
39.                 if (data[x+d->next->dx][y+d->next->dy]==0) d=d->next;
40.                 else return;
41.         }
42.                 data[x+d->dx][y+d->dy]=i;
43.                 i++;
44.                 findway(d,x+d->dx,y+d->dy,data);
45. }

复制代码

Arthur.Echo

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. 
   
5. int main(int argc,char *argv[])
   
6. {
   
7.         int num;
   
8.         int i = 0;
   
9.         int j = 0;
   
10. 
    
11.         if(argc < 2)
    
12.         {
    
13.                 printf("Usage: print_cycle_number number, where number is a positive int number\n");
    
14.                 exit(1);
    
15.         }
    
16. 
    
17.         num = atoi(argv[1]);
    
18.         if(num <= 0)
    
19.         {
    
20.                 printf("Usage: print_cycle_number number , where number is a positive int number\n");
    
21.                 exit(1);
    
22.         }
    
23. 
    
24. 
    
25.         for(;j < num ;j++)
    
26.         {
    
27.                 for(i = 0;i < num ;i++)
    
28.                 {
    
29.                         if(i >= j && i + j <= num - 1)
    
30.                                 // j cycle
    
31.                                 printf("%5d",4 * (num - j) * j + i - j + 1);
    
32.                         else if(i > j && i + j >= num - 1)
    
33.                                 // num - 1 - i cycle
    
34.                                 printf("%5d",(4 * (1 + i) * (num - 1 - i) + 1) + num - 2 * (num - 1 - i) - 1 + j - (num - 1 -i));
    
35.                         else if(i <= j && i + j > num - 1)
    
36.                                 // num - 1 - j cycle
    
37.                                 printf("%5d",4 * (1 + j) * (num - 1 -j) + (num - 2 * (num - 1 - j) - 1) * 2 + num - i - (num - 1 - j));
    
38.                         else if(i < j && i + j <= num - 1)
    
39.                                 // i cycle
    
40.                                 printf("%5d", 4 * (num - i) * i + (num - 2 * i - 1) * 3 + num  - i - j);
    
41.                 }
    
42.                 printf("\n");
    
43.         }
    
44. 
    
45.         return 0;
    
46. }
    

复制代码

运行结果

1. [root@arthur program]# ./print_cycle_number 20
   
2.     1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20
   
3.    76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   21
   
4.    75  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160   95   22
   
5.    74  143  204  205  206  207  208  209  210  211  212  213  214  215  216  217  218  161   96   23
   
6.    73  142  203  256  257  258  259  260  261  262  263  264  265  266  267  268  219  162   97   24
   
7.    72  141  202  255  300  301  302  303  304  305  306  307  308  309  310  269  220  163   98   25
   
8.    71  140  201  254  299  336  337  338  339  340  341  342  343  344  311  270  221  164   99   26
   
9.    70  139  200  253  298  335  364  365  366  367  368  369  370  345  312  271  222  165  100   27
   
10.    69  138  199  252  297  334  363  384  385  386  387  388  371  346  313  272  223  166  101   28
    
11.    68  137  198  251  296  333  362  383  396  397  398  389  372  347  314  273  224  167  102   29
    
12.    67  136  197  250  295  332  361  382  395  400  399  390  373  348  315  274  225  168  103   30
    
13.    66  135  196  249  294  331  360  381  394  393  392  391  374  349  316  275  226  169  104   31
    
14.    65  134  195  248  293  330  359  380  379  378  377  376  375  350  317  276  227  170  105   32
    
15.    64  133  194  247  292  329  358  357  356  355  354  353  352  351  318  277  228  171  106   33
    
16.    63  132  193  246  291  328  327  326  325  324  323  322  321  320  319  278  229  172  107   34
    
17.    62  131  192  245  290  289  288  287  286  285  284  283  282  281  280  279  230  173  108   35
    
18.    61  130  191  244  243  242  241  240  239  238  237  236  235  234  233  232  231  174  109   36
    
19.    60  129  190  189  188  187  186  185  184  183  182  181  180  179  178  177  176  175  110   37
    
20.    59  128  127  126  125  124  123  122  121  120  119  118  117  116  115  114  113  112  111   38
    
21.    58   57   56   55   54   53   52   51   50   49   48   47   46   45   44   43   42   41   40   39
    

复制代码

bineon

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. 
   
5. int direction = 1;        // 1右        2下        3左        4上
   
6. 
   
7. int main(int argc, char **argv)
   
8. {
   
9.         int count, i, j, tmp;
   
10.         int N = (argc == 2) ? atoi(argv[1]) : 10;
    
11.        
    
12.     tmp = 0;
    
13.     i = j = 0;        
    
14.     count = N * N;
    
15.     int result[N][N];
    
16.     memset(result, 0, count * sizeof(int));
    
17. 
    
18.     while(tmp++ < count)
    
19.     {
    
20.         result[i][j] = tmp;
    
21.         switch(direction)
    
22.         {
    
23.             case 1:
    
24.                 if (j == N - 1 || result[i][j + 1] > 0)
    
25.                 {
    
26.                     i++;
    
27.                     direction = 2;
    
28.                 }   
    
29.                 else
    
30.                 {
    
31.                     j++;
    
32.                 }   
    
33.                 break;
    
34.             case 2:
    
35.                 if (i == N - 1 || result[i + 1][j] > 0)
    
36.                 {
    
37.                     j--;
    
38.                     direction = 3;
    
39.                 }   
    
40.                 else
    
41.                 {
    
42.                     i++;
    
43.                 }   
    
44.                 break;
    
45.             case 3:
    
46.                 if (j == 0 || result[i][j - 1] > 0)
    
47.                 {
    
48.                     i--;
    
49.                     direction = 4;
    
50.                 }   
    
51.                 else
    
52.                 {
    
53.                     j--;
    
54.                 }   
    
55.                 break;
    
56.             case 4:
    
57.                 if (result[i - 1][j] > 0)
    
58.                 {
    
59.                     direction = 1;
    
60.                     j++;
    
61.                 }   
    
62.                 else
    
63.                 {
    
64.                     i--;
    
65.                 }   
    
66.                 break;
    
67.             default:
    
68.                 break;
    
69.         }   
    
70.     }  
    
71.     for (i = 0; i < N; i++)
    
72.     {
    
73.         for (j = 0; j < N; j++)
    
74.         {
    
75.             printf("%d\t", result[i][j]);
    
76.         }   
    
77.         printf("\n");
    
78.     }   
    
79.    
    
80.     getchar();
    
81.       
    
82. }

复制代码