一道安捷伦笔试题

bluemy

用C编写程序并注释
N*N矩阵输出
N=3时输出
1 2 3
  8 9 4
  7 6 5
N＝4时输出
   1  2  3   4
   12 13 14  5
   11 16 15  6
   10  9  8  7

编写当N时的输出

gangjh

写出来了吗？

ngzyl

阿，强。。。。。。等我来想想

王紫豪

very easy 好像以前讨论过

svenwang

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. 
   
6. enum {
   
7.         MASK_UP                = 1,
   
8.         MASK_DOWN        = 2,
   
9.         MASK_LEFT        = 4,
   
10.         MASK_RIGHT        = 8,
    
11.        
    
12.         TURN_NONE        = 0,
    
13.         TURN_UP                = 1,
    
14.         TURN_DOWN        = 2,
    
15.         TURN_LEFT        = 3,
    
16.         TURN_RIGHT        = 4,
    
17. };
    
18. 
    
19. int directs[5][2] = {
    
20.         {0, 0},                // 0:TURN_NONE
    
21.         {-1, 0},        // 1:TURN_UP
    
22.         {1, 0},                // 2:TURN_DOWN
    
23.         {0, -1},        // 3:TURN_LEFT
    
24.         {0, 1},                // 4:TURN_RIGHT
    
25. };
    
26. 
    
27. int rules[16] = {
    
28.         TURN_NONE,        // 0:none
    
29.         TURN_UP,        // 1:up
    
30.         TURN_DOWN,        // 2:down
    
31.         TURN_NONE,        // 3:invalid
    
32.         TURN_LEFT,        // 4:left
    
33.         TURN_LEFT,        // 5:left and up
    
34.         TURN_DOWN,        // 6:left and down
    
35.         TURN_NONE,        // 7:invalid
    
36.         TURN_RIGHT,        // 8:right
    
37.         TURN_UP,        // 9:right and up
    
38.         TURN_RIGHT,        // 10:right and down
    
39.         TURN_NONE,        // 11-15:invalid
    
40. };
    
41. int next_pos(int *matrix, int n, int i, int j, int *nexti, int *nextj)
    
42. {
    
43.         if (i == -1 || j == -1)
    
44.         {
    
45.                 *nexti = 0;
    
46.                 *nextj = 0;
    
47.                 return 1;
    
48.         }
    
49.         int mask = 0;
    
50.         if (i - 1 >= 0 && matrix[(i - 1) * n + j] == 0)                // up ok
    
51.                 mask |= MASK_UP;
    
52.         if (i + 1 <= n - 1 && matrix[(i + 1) * n + j] == 0)        // down ok
    
53.                 mask |= MASK_DOWN;
    
54.         if (j - 1 >= 0 && matrix[i * n + (j - 1)] == 0)                // left ok
    
55.                 mask |= MASK_LEFT;
    
56.         if (j + 1 <= n - 1 && matrix[i * n + (j + 1)] == 0)        // right ok
    
57.                 mask |= MASK_RIGHT;
    
58.        
    
59.         int rule = rules[mask];
    
60.         int *direct = directs[rule];
    
61.         if (direct[0] == 0 && direct[1] == 0)
    
62.                 return 0;
    
63.         *nexti = i + direct[0];
    
64.         *nextj = j + direct[1];
    
65.         return 1;
    
66. }
    
67. 
    
68. int main(int argc, char *argv[])
    
69. {
    
70.         if (argc != 2)
    
71.                 return -1;
    
72.         int n = atoi(argv[1]);
    
73.         if (n <= 0)
    
74.                 return -1;
    
75.        
    
76.         int *matrix = (int*)malloc(n * n * sizeof(int));
    
77.         memset(matrix, 0, n * n * sizeof(int));
    
78. 
    
79.         int i = -1;
    
80.         int j = -1;
    
81.         int value = 1;
    
82.         while (next_pos(matrix, n, i, j, &i, &j) != 0)
    
83.         {
    
84.                 matrix[i * n + j] = value++;
    
85.         }
    
86. 
    
87.         for (i = 0; i < n; i++)
    
88.         {
    
89.                 for (j = 0; j < n; j++)
    
90.                 {
    
91.                         printf("%d", matrix[i * n + j]);
    
92.                         if (j != n - 1)
    
93.                                 printf("\t");
    
94.                 }
    
95.                 printf("\n");
    
96.         }
    
97.        
    
98.         free(matrix);
    
99.         return 0;
    
100. }
     

复制代码

lknh17

数组类的经典题目

jronald

1. 
   
2. #include <stdio.h>
   
3. 
   
4. //get a matrix of n*n
   
5. int* get_ma(int n)
   
6. {
   
7.         int *a=new int[n*n];
   
8. 
   
9.         int nr=0;
   
10.         int x=0;
    
11.         int y=0;
    
12.         int dx=1;
    
13.         int dy=0;
    
14.         //boundaries
    
15.         int u=0;
    
16.         int d=n-1;
    
17.         int l=0;
    
18.         int r=n-1;
    
19. 
    
20.         int nn=n*n;
    
21.         while (nr<nn) {
    
22.                 a[x+n*y]=nr;
    
23.                 if (dx>0 && x==r) {
    
24.                         dx=0;
    
25.                         dy=1;
    
26.                         ++u;
    
27.                 } else if (dx<0 && x==l) {
    
28.                         dx=0;
    
29.                         dy=-1;
    
30.                         --d;
    
31.                 }
    
32.                 if (dy>0 && y==d) {
    
33.                         dx=-1;
    
34.                         dy=0;
    
35.                         --r;
    
36.                 } else if (dy<0 && y==u) {
    
37.                         dx=1;
    
38.                         dy=0;
    
39.                         ++l;
    
40.                 }
    
41.                 x+=dx;
    
42.                 y+=dy;
    
43.                 ++nr;
    
44.         }
    
45. 
    
46.         return a;
    
47. }
    
48. 
    
49. int main(int argc, char* argv[])
    
50. {
    
51.         const int n=4;       
    
52.         int *a=get_ma(n);
    
53.         for (int i=0;i<n*n;++i) {
    
54.                 printf("%d\t",a[i]);
    
55.                 if ((i+1)%n==0) {
    
56.                         putchar('\n');
    
57.                 }
    
58.         }
    
59.         delete a;
    
60.         return 0;
    
61. }
    

复制代码

[ 本帖最后由 jronald 于 2006-11-23 14:14 编辑 ]

zhangxiangod

#include <stdio.h>
#include <math.h>
#define NUM 5
int main(){

    int a[10][10];
    int n;
    int i,j;
    int number,number_flag,flag;
    int begin,end;
    n=NUM;
    number=1;
    number_flag=n*n;
    i=0;j=0;
    flag=0;
    begin=0;end=n-1;
    while(number_flag!=0){
        if(flag==0){
            if(j==end){
                a[i][j] = number;
                number++;
                i++;
                flag=1;
                number_flag--;
                continue;
            }else{
                a[i][j] = number;
                number++;
                j++;
            }
        }

         if(flag==1){
            if(i==end){
                a[i][j] = number;
                number++;
                j--;
                flag=2;
                number_flag--;
                continue;
            }else{
                a[i][j] = number;
                number++;
                i++;
            }
        }
        if(flag==2){
            if(j==begin){
                a[i][j] = number;
                number++;
                i--;
                flag=3;
                number_flag--;
                continue;
            }else{
                a[i][j] = number;
                number++;
                j--;
            }
        }

        if(flag==3){
            if(i==begin+1){

                a[i][j] = number;
                number++;
                j++;
                flag=0;

                end--;
                begin++;
                number_flag--;
                continue;

            }else{
                a[i][j] = number;
                number++;
                i--;
            }
        }
        number_flag--;

    }
    n=NUM;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

bluemy

谢谢大家！

hqx8211

不用那么复杂。观察一下规律就可以发现（假定N＝5，其它值一样分析法）：
赋值转弯的次数分别为"4, 4, 4, 3, 3, 2, 2, 1, 1",如果N ＝ 10， 则为"9, 9, 9, 8, 8, .....3, 2, 2, 1, 1"

程序如下，由于个人感觉本题重在考思路，因此直接使用数组，没有用二维指针动态分配，也只进行了一些基本的错误检查。
#include "test.h"
extern int errno;

typedef struct
{
        int line;
        int row;
}TURN;
#define MAX 10

int main(int argc, char *argv[])
{
        int line = 0, row = 0, flg = 0, pp_num[MAX][MAX];
        int turn_count, N;
        int i, j, k;
        TURN turn[4] =
        {
                {0, 1},
                {1, 0},
                {0, -1},
                {-1, 0}
        };

        //N由参数输入，范围1 - 10
        if ((2 != argc) || ((N = atoi(argv[1])) < 1) || (atoi(argv[1]) > 10))
        {
                printf("Usage : %s (1 - 10)\n", argv[0]);
                return (1);
        }

        //给二维数组赋值
        for (i = 1, turn_count = N - 1, j = 0, k = -1; i <= N * N; i++)
        {
                pp_num[line][row] = i;
                line += turn[flg].line;
                row += turn[flg].row;

                //累积到turn_count次就"转弯"
                if (++j == turn_count)
                {
                        flg = (flg + 1) % 4;
                        ++k;
                        j = 0;
                }
                //每转弯两次，就减少turn_count。第一次要转弯三次才减少turn_count,所以k初始值为-1
                if (2 == k)
                {
                        k = 0;
                        --turn_count;
                }

        }

        for (i = 0; i < N; i++)
        {
                for (j = 0; j < N; j++)
                {
                        printf("%3d  ", pp_num[i][j]);
                }
                printf("\n");
        }

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