趣味编程 - 矩阵生成

rain_fish

唉，老了

ecjtubaowp

反向螺旋矩阵

wb112200

{:3_183:} 以为是做3D运算的呢...

放纵思想

我还以为横、竖、斜向相加相等呢。

yg

1. #include <stdio.h>
   
2. #include <unistd.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. #include <errno.h>
   
6. 
   
7. #define GET_XY(x,y,n)   ((y)*(n)+(x))
   
8. 
   
9. char *Cmd;
   
10. 
    
11. struct mm
    
12. {
    
13.     int x;
    
14.     int y;
    
15. } Mm[4] = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
    
16. 
    
17. void
    
18. rotate_mm( int r )
    
19. {
    
20.     struct mm m;
    
21. 
    
22.     r %= 4;
    
23.     if( r == 1 )
    
24.     {
    
25.         m = Mm[0];
    
26.         Mm[0] = Mm[1];
    
27.         Mm[1] = Mm[2];
    
28.         Mm[2] = Mm[3];
    
29.         Mm[3] = m;
    
30.     }
    
31.     else if( r == 2 )
    
32.     {
    
33.         m = Mm[0];
    
34.         Mm[0] = Mm[2];
    
35.         Mm[2] = m;
    
36.         m = Mm[1];
    
37.         Mm[1] = Mm[3];
    
38.         Mm[3] = m;
    
39.     }
    
40.     else if( r == 3 )
    
41.     {
    
42.         m = Mm[0];
    
43.         Mm[0] = Mm[3];
    
44.         Mm[3] = Mm[2];
    
45.         Mm[2] = Mm[1];
    
46.         Mm[1] = m;
    
47.     }
    
48. 
    
49.     return;
    
50. }
    
51. 
    
52. int *
    
53. make_matrix( int n )
    
54. {
    
55.     int *im;
    
56.     int i;
    
57.     int x, y;
    
58.     int m;
    
59.     int d, l;
    
60. 
    
61.     if( ( n - 1 ) % 2 )
    
62.     {
    
63.         fprintf( stderr, "[%d] is not odd!\n", n );
    
64.         return( (int *) NULL );
    
65.     }
    
66. 
    
67.     if( ( im = (int *) malloc( n*n*sizeof(int) ) ) == (int *) NULL )
    
68.     {
    
69.         fprintf( stderr, "malloc error: %s\n", strerror(errno) );
    
70.         return( (int *) NULL );
    
71.     }
    
72. 
    
73.     x = y = n / 2;
    
74.     m = 0;
    
75.     d = 0;
    
76.     l = 1;
    
77. 
    
78.     for( i = 1; i <= n*n; i++ )
    
79.     {
    
80.         im[GET_XY(x,y,n)] = i;
    
81.         x += Mm[m].x;
    
82.         y += Mm[m].y;
    
83.         if( ++d == l )
    
84.         {
    
85.             if( m % 2 )
    
86.                 l++;
    
87.             m = ( m + 1 ) % 4;
    
88.             d = 0;
    
89.         }
    
90.     }
    
91. 
    
92.     return( im );
    
93. }
    
94. 
    
95. int
    
96. get_digits( int n )
    
97. {
    
98.     if( n / 10 )
    
99.         return( get_digits( n / 10 ) + 1 );
    
100.     else
     
101.         return( 1 );
     
102. }
     
103. 
     
104. static void
     
105. prt_help()
     
106. {
     
107.     fprintf( stderr, "Usage：%s [-r type] [-h] num\n", Cmd );
     
108. 
     
109.     return;
     
110. }
     
111. 
     
112. int
     
113. main( int ac, char **av )
     
114. {
     
115.     int c;
     
116.     int errflag = 0;
     
117.     int r = 0;
     
118.     int *im;
     
119.     int n;
     
120.     int d;
     
121.     int i;
     
122. 
     
123.     if( ( Cmd = strrchr( av[0], '/' ) ) == NULL )
     
124.         Cmd = av[0];
     
125.     else
     
126.         Cmd++;
     
127. 
     
128.     while( ( c = getopt( ac, av, ":hr:" ) ) != -1 )
     
129.     {
     
130.         switch( c )
     
131.         {
     
132.             case 'r':
     
133.                 r = atoi(optarg);
     
134.                 if( r < 1 || r > 3 )
     
135.                 {
     
136.                     fprintf( stderr, "%s: type in 1,3\n", Cmd );
     
137.                     errflag++;
     
138.                 }
     
139.                 break;
     
140.             case 'h':
     
141.                 errflag++;
     
142.                 break;
     
143.             case ':':        /* argument for option is missing */
     
144.                 errflag++;
     
145.                 fprintf( stderr, "%s: option -%c need argument\n",
     
146.                                 Cmd, optopt );
     
147.                 break;
     
148.             case '?':        /* option is not in option set */
     
149.                 errflag++;
     
150.                 fprintf( stderr, "%s: option -%c is unknown \n",
     
151.                                 Cmd, optopt);
     
152.         }
     
153.     }
     
154. 
     
155.     if( errflag )
     
156.     {
     
157.         prt_help( );
     
158.         exit( 1 );
     
159.     }
     
160. 
     
161.     if( optind != ac - 1 )
     
162.     {
     
163.         prt_help( );
     
164.         exit( 1 );
     
165.     }
     
166. 
     
167.     n = atoi(av[optind]);
     
168. 
     
169.     if( r )
     
170.         rotate_mm( r );
     
171. 
     
172.     if( ( im = make_matrix( n ) ) == (int *) NULL )
     
173.     {
     
174.         fprintf( stderr, "%s: make_matrix error!\n", Cmd );
     
175.         exit( 1 );
     
176.     }
     
177. 
     
178.     d = get_digits( n * n );
     
179. 
     
180.     printf( "%d\n", n );
     
181.     for( i = 0; i < n*n; i++ )
     
182.     {
     
183.         printf( "%-*d ", d, *im++ );
     
184.         if( i % n == n - 1 )
     
185.             printf( "\n" );
     
186.     }
     
187.     printf( "\nIt's OK\n" );
     
188. 
     
189.     free( im - n * n );
     
190. 
     
191.     return( 0 );
     
192. }

复制代码

用以前的程序架构完成的，算法部分其实很简单，人是怎么想的，程序就怎么跑

daybreakcx

回复 3# baozhao

其实都一样，是一圈圈往里过渡的，主要是定位i行j列实在第几圈，就像程序里头的c值，然后就是定位在圈中的什么位置，对应输出即可，主要是怎么省空间

koolcoy

换一种想法，这个题目特别简单，当然前提时O(n^2)的空间复杂度可以接受

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. enum Direction {
   
6.         DOWN, RIGHT, UP, LEFT
   
7. };
   
8. 
   
9. void getNextCell(int side, int* matrix, int& x, int& y, Direction& direction) {
   
10.         switch (direction) {
    
11.         case DOWN:
    
12.                 if (y < side - 1 && matrix[side * (y + 1) + x] == 0) {
    
13.                         ++y;
    
14.                 } else {
    
15.                         direction = RIGHT;
    
16.                         ++x;
    
17.                 }
    
18.                 break;
    
19.         case RIGHT:
    
20.                 if (x < side - 1 && matrix[side * y + x + 1] == 0) {
    
21.                         ++x;
    
22.                 } else {
    
23.                         direction = UP;
    
24.                         --y;
    
25.                 }
    
26.                 break;
    
27.         case UP:
    
28.                 if (y > 0 && matrix[side * (y - 1) + x] == 0) {
    
29.                         --y;
    
30.                 } else {
    
31.                         direction = LEFT;
    
32.                         --x;
    
33.                 }
    
34.                 break;
    
35.         case LEFT:
    
36.                 if (x > 0 && matrix[side * y + x - 1] == 0) {
    
37.                         --x;
    
38.                 } else {
    
39.                         direction = DOWN;
    
40.                         ++y;
    
41.                 }
    
42.                 break;
    
43.         }
    
44. }
    
45. 
    
46. int main(int argc, char** argv) {
    
47.         int side = 0;
    
48.         if (argc != 2 || sscanf(argv[1], "%d", &side) != 1
    
49.                         || side % 2 != 1 || side <= 0) {
    
50.                 printf("Invalid input\n");
    
51.                 return 1;
    
52.         }
    
53.         int matrixSize = side * side;
    
54. 
    
55.         int* matrix = (int*)calloc(sizeof(int) * matrixSize, 1);
    
56. 
    
57.         int x = 0;
    
58.         int y = 0;
    
59.         int value = matrixSize;
    
60.         Direction direction = DOWN;
    
61.         do {
    
62.                 matrix[y * side + x] = value;
    
63.                 --value;
    
64.                 getNextCell(side, matrix, x, y, direction);
    
65.         } while (!(x == side / 2 && y == side / 2));
    
66. 
    
67.         matrix[y * side + x] = 1;
    
68. 
    
69.         for (int i = 0; i < side; ++i) {
    
70.                 for (int j = 0; j < side; ++j) {
    
71.                         printf("%4d ", matrix[i * side + j]);
    
72.                 }
    
73.                 printf("\n");
    
74.         }
    
75. 
    
76.         return 0;
    
77. }
    

复制代码

johntsu

呵呵，螺旋矩阵的问题，哥好多年以前也玩过。