《算法竞赛入门经典》第三章 3.1

程序 3-1

 1 #include<stdio.h>
 2 #define MAXN 100 + 10
 3 int a[MAXN];
 4 int main()
 5 {
 6     int i, x, n = 0;
 7     while(scanf("%d", &x) == 1)
 8         a[n++] = x;
 9     for(i = n-1; i>=1; i--)
10     {
11         printf("%d ", a[i]);
12     }
13     printf("%d
", a[0]);
14     return 0;
15 }

　　上面的输出方法在考研复试，王道机试遇到多次。。

　　不过这次打字出错结果总是运行时错误。

提示3-2

　　如果放在main内部，将100换成100000（5个0）还是可以的，1000000（6个0）则真的异常退出。放在main之上，没有这个问题。

程序3-2

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MAXN 1000 + 10
 4 int a[MAXN];
 5 int main()
 6 {
 7     int i, j, n, k, first = 1;
 8     memset(a, 0, sizeof(a));
 9     scanf("%d%d", &n, &k);
10     for(i = 1; i <=k; i++)
11         for(j = 1; j <=n; j++)
12             if(j % i ==0)
13                 a[j] = !a[j];
14     for(i = 1; i <=n; i++)
15         if(a[i])
16         {
17             if(first)
18                 first = 0;
19             else
20                 printf(" ");
21             printf("%d", i);
22         }
23     return 0;
24 }

　　这个输出技巧和程序3-1的输出技巧区别在于，3-1的程序要求知道倒数第二个元素的index，而后者3-2则更一般，后者可适用更多情况。

程序3-3

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MAXN 10
 4 int a[MAXN][MAXN];
 5 int main()
 6 {
 7     int n, x, y, tot = 0;
 8     scanf("%d", &n);
 9     memset(a, 0, sizeof(a));
10     tot = a[x=0][y=n-1] = 1;
11     while(tot < n*n)
12     {
13         while(x+1<n && !a[x+1][y]) a[++x][y] = ++tot;
14         while(y-1>=0 && !a[x][y-1]) a[x][--y] = ++tot;
15         while(x-1>=0 && !a[x-1][y]) a[--x][y] = ++tot;
16         while(y+1<n && !a[x][y+1]) a[x][++y] =  ++tot;
17 
18     }
19     for(x = 0; x < n; x++)
20     {
21         for(y = 0; y < n; y++)
22             printf("%3d", a[x][y]);
23             printf("
");
24     }
25     return 0;
26 }