2018级航空航天类《C语言程序设计》上机考试 A卷试题（回忆版）

以下提供的 AC 代码可能不是最简的思路和代码实现，仅供参考！

A 向量的模长

试题大意

输入一个 n 维向量，求这个向量的模长的平方。

样例输入

3
1 2 3

样例输出

14

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
int n;
int a[1005];
int len()
{
    int s = 0;
    int i;
    for (i = 0; i < n; i++)
        s += a[i] * a[i];
    return s;
}
int main()
{
    int i;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("%d\n", len());
    return 0;
}

作答提示

要求求的是模长的平方，得到的结果直接就是整数，不需要用浮点数，不需要开平方。

更进一步，对顺序输入的元素求平方和可以不需要数组。更简单的参考代码：

#include <stdio.h>
int main() {
    int n, i, x, s = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &x);
        s += x * x;
    }
    printf("%d\n", s);
    return 0;
}

B 质因数分解

题目大意

给定一个整数 p，保证该数是 2 个质数的乘积（即 $p=p_1 \cdot p_2$，$p_1<p_2$），求较大的质因子 $p_2$。

样例输入

21

样例输出

7

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
int main()
{
    int n, i;
    scanf("%d", &n);
    for (i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            break;
    }
    printf("%d\n", n / i);
    return 0;
}

作答提示

这道题给的限定条件相当严格，所以其实可用来输入的整数的个数是相当有限的。千万不要担心有不符合 $p=p_1 \cdot p_2$ 的输入数据。要求输出 $p_2$ 可以先找出 $p_1$ （因为 $p_1$ 比较小，比较容易找，找的范围是到 $\sqrt{n}$ 即可）。

直接从 2 循环到 n 也是可以的，因为遇到 $p_1$ 就 break 了，实际的循环不会真正执行到 $\sqrt{n}$ 以后。

C 加权平均分

题目大意

给出一些门课的得分（百分制）和这门课的学分数，求加权平均分。输入为每行 2 个整数，分别表示一门课程的学分数量和百分制得分。输出加权平均分保留 2 位小数。

特别注意：如果总学分数为零，则加权平均为零分（ 0.00 ）。

样例输入

6 98
4 93
2 88

样例输出

94.67

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
int a[105], v[105];
int sumv, sum;
int main()
{
    int ai, vi;
    while (scanf("%d%d", &vi, &ai) != EOF)
    {
        sum += ai * vi;
        sumv += vi;
    }
    if (sumv) printf("%.2lf\n", sum * 1.0 / sumv);
    else printf("0.00\n");
    return 0;
}

作答提示

输入数据是没有给学科数量的，也就是输入的行数是 不确定 的，请用 while(scanf(...) != EOF) 输入数据。另外，在本机调试的过程中，当你输入完所有的数据，程序是不会马上有反应的，因为你没有给出n，计算机不知道你输入的数据到底有多少行，所以会一直等着你输入。此时请用 Ctrl+Z 终止输入（控制台会显示一个符号 ^Z，然后再按回车就可以看到输出结果了），^Z 这个符号代表 EOF。

另外注意判断总学分数是否为零。第一次忘了加判断就 WA 了一个点。

D 十六进制编辑器

题目大意

以十六进制(大写)，2 位一组给出 n 个 8-bit 整数（以一行字符串的形式给出）。

有若干组查询，每个查询给出 $x$ 和 $y$ 两个整数，要输出第 $x$ 个数和第 $y$ 个数的乘积(十进制)。

输入数据第一行是 $n$；第二行是一个长度为 $2n$ 的字符串（仅包含数字和大写字母 A-F）；第三行是 $m$ 表示 $m$ 次查询，接下来 $m$ 行每行 2 个整数 $x$ 和 $y$。

对于每次查询，输出一个整数，为第 $x$ 个数和第 $y$ 个数的乘积（下标从零开始）

样例输入

8
8AE45CF173BB6A2E
5
1 4
0 2
2 7
3 6
4 5

样例输出

26220
12696
4232
25546
21505

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
int hextodec(char x1, char x2)
{
    int d1, d2;
    if (isdigit(x1))d1 = x1 - '0';
    else if (x1 >= 'A' && x1 <= 'F')d1 = x1 - 'A' + 10;
    if (isdigit(x2))d2 = x2 - '0';
    else if (x2 >= 'A' && x2 <= 'F')d2 = x2 - 'A' + 10;
    return d1 * 16 + d2;
}
int n, m;
int a[10005];
int main()
{
    int i;
    char c1, c2;
    int x, y;
    scanf("%d", &n);
    while (getchar() != '\n');
    for (i = 0; i < n; i++)
    {
        c1 = getchar();
        c2 = getchar();
        a[i] = hextodec(c1, c2);
    }
    scanf("%d", &m);
    for (i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        printf("%d\n", a[x] * a[y]);
    }
    return 0;
}

作答提示

先把输入的长度为 $2n$ 的字符串所表达的 $n$ 个十六进制整数存入 int 数组，然后处理对于乘积的查询。

E 忽略大小写的子串匹配

题目大意

给俩字符串，一行一个（均不包含空白字符），判断第一个字符串是不是第二个字符串的子串，如果是的话输出子串最先出现的位置，如果不是子串输出错误信息。

样例输入

hAnG
BeiHangUniversity

BuAA
ACcoding.cn

样例输出

Yes:4

Emmm

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
char key[1005], str[1005];
char key2[1005], str2[1005]; //lowercase
int main()
{
    int i;
    char *ret = NULL;
    scanf("%s", key);
    scanf("%s", str);
    for (i = 0; key[i]; i++)
        key2[i] = tolower(key[i]);
    for (i = 0; str[i]; i++)
        str2[i] = tolower(str[i]);
    ret = strstr(str2, key2);
    if (ret != NULL)
        printf("Yes:%d\n", ret - str2 + 1);
    else
        printf("Emmm\n");
    return 0;
}

作答提示

因为题目说了字符串不带空白字符，所以不要用 gets ，优先选用 scanf 。如果用了 gets 一定要检验字符串末尾有没有 '\r' ，否则会错的很惨。 Windows 系统和 Linux 系统的默认换行符不同，想要详细了解可以问助教或者上网查。

用库函数 strstr 匹配子串，要熟悉。此题由于忽略大小写，所以将输入的字符串全部转换为小写再匹配。

F 扫雷

题目大意

给一个 $m*n$ 的字符方阵，每个格有地雷或者没有地雷，然后输出一个 $m*n$ 的整数方阵，求出每个格子周围的地雷数量（以该格子为中心的九宫格内地雷数量）

我忘了"没有地雷"是什么符号表示了，可能是 '.' 或者 'N' 吧，然后有地雷的符号根据我的AC代码反推回去应该是用 'Y' 表示的。

样例输入

3 4
..Y.
.Y..
Y...

样例输出

1 2 2 1
2 3 2 1
2 2 1 0

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
int n, m;
char mp[105][105];
int cnt[105][105];
typedef struct Point
{
    int x, y;
}Point;
Point nil, dir[9] = {
    {-1,-1}, {-1, 0}, {-1, 1},
    {0, -1}, {0, 0}, {0, 1},
    {1, -1}, {1, 0}, {1, 1}
};
Point mkpt(int x, int y)
{
    Point ret;
    ret.x = x, ret.y = y;
    return ret;
}
Point padd(Point a, Point b)
{
    Point ret;
    ret.x = a.x + b.x;
    ret.y = a.y + b.y;
    return ret;
}
int inLim(Point ct)
{
    return (ct.x >= 0 && ct.x < n) && (ct.y >= 0 && ct.y < m);
}
int cntt(Point ct)
{
    int i, ret = 0;
    for (i = 0; i < 9; i++)
    {
        Point pt = padd(ct, dir[i]);
        if (inLim(pt) && mp[pt.x][pt.y] == 'Y')
            ret++;
    }
    return ret;
}
int main()
{
    int i, j;
    scanf("%d%d", &n, &m);
    for (i = 0;i < n; i++)
        scanf("%s", mp[i]);
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            cnt[i][j] = cntt(mkpt(i, j));
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
        printf("%d%c", cnt[i][j], j == m-1 ? 10 : 32);
    return 0;
}

作答提示

循环，然后注意一下如何处理边界。

输出的时候每行 m 个整数，中间空格隔开，最后尽量不要留多余的空格（不确定会不会PE）。

G 扑克统计

题目大意

给一堆扑克牌的信息，统计当前桌面上现有的牌能凑出几套完整的扑克牌。

多组输入数据

每组输入数据先给一个 n 表示当前桌面上牌的张数，然后每行 2 个整数，分别表示花色（1 到 4 的整数）和牌面（1 到 13 的整数）。输出一个整数表示能凑出来多少张牌。

一副完整扑克牌的标准是 52 张，四种花色每种 13 张。

样例输入

2
13
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
2 13
52
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13

样例输出

0
1

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
int cnt[5][14];
int check()
{
    int ret = 0x7FFFFFFF;
    int i, j;
    for (i = 1; i <= 4; i++)
        for (j = 1; j <= 13; j++)
    {
        if (cnt[i][j] < ret)ret = cnt[i][j];
    }
    return ret;
}
int main()
{
    int T, n;
    int pat, pid;
    scanf("%d", &T);
    while (T--)
    {
        memset(cnt, 0, sizeof(cnt));
        scanf("%d", &n);
        while (n--)
        {
            scanf("%d%d", &pat, &pid);
            cnt[pat][pid]++;
        }
        printf("%d\n", check());
    }
    return 0;
}

作答提示

散列表计数。凑扑克牌是木桶（短板）原理，数量最少的花色+牌面的数量就是答案。

H 多项式求导

题目大意

给一个多项式，求其导函数。

输入输出格式参考样例，一次项和零次项均严格按照格式给出。

输出的时候首项如果是正的不要有 + 号。

样例输入

4*x^4-3*x^2+5*x^1+2*x^0

样例输出

16*x^3-6*x^1+5*x^0

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
typedef struct Elem
{
    int k, p;
}Elem;
Elem F[105];
int mxp;
Elem mkelm(int kk, int pp)
{
    Elem ret;
    ret.k = kk, ret.p = pp;
    return ret;
}
int main()
{
    int k, p, i;
    int flg = 0;
    while (scanf("%d*x^%d", &k, &p) == 2)
    {
        Elem fx = mkelm(k, p);
        if (k == 0 || p == 0)continue;
        if (p > mxp) mxp = p;
        if (F[p].p == 0)F[p].p = p;
        F[p].k += fx.k;
    }
    for (i = mxp; i > 0; i--)//f'
    {
        Elem fi = F[i];
        if (F[i].p != i)continue;
        fi.k *= fi.p, fi.p--;
        if (fi.k)
            printf("%s%d*x^%d", flg && fi.k > 0 ? "+" : "", fi.k, fi.p), flg = 1;
    }
    if (!flg)
        printf("0");
    return 0;
}

作答提示

就是注意输入的时候用 scanf 控制好格式（每一项的格式为 %d*x^%d ），然后注意一下可能有合并同类项（样例是我现编的，我懒得编那种需要合并的数据了）。输出的时候也是控制好格式就行了。

多项式的题平时上机和练习赛练过两次，主要还是考察 scanf 的格式化输入。

I 高精度减法

题目大意

输入俩超大整数（ $A, B \leq 10^{500}$ ），可能有前导零，不保证 $A\geq B$ 。输出它们的差。

样例输入

1000
999

样例输出

1

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
char s1[505], s2[505];
int a[505], b[505];
int res[505];
int l1, l2, l;
int numcmp()
{
    int i;
    if (l1 > l2)return 1;
    else if (l1 < l2)return -1;
    else
    {
        for (i = l1; i >= 0; i--)
        {
            if (a[i] > b[i])return 1;
            else if (a[i] < b[i])return -1;
        }
    }
    return 0;
}
int hgint_minus(int *r, int *A, int l1, int *B, int l2)//A - B
{
    int l = l1 > l2 ? l1 : l2;
    int i;
    for (i = 0; i < l; i++)
    {
        r[i] += A[i] - B[i];
        while (r[i] < 0)
            r[i] += 10, r[i+1]--;
    }
    while (r[l-1] == 0)l--;
    return l;
}
int main()
{
    int i;
    int flg = 0;
    scanf("%s%s", s1, s2);
    l1 = strlen(s1), l2 = strlen(s2);
    for (i = 0; i < l1; i++)
        a[i] = s1[l1 - i - 1] - '0';
    for (i = 0; i < l2; i++)
        b[i] = s2[l2 - i - 1] - '0';
    while (a[l1 - 1] == 0)l1--;
    while (b[l2 - 1] == 0)l2--;
    flg = numcmp();
    if (flg == 0)
        l = 1;
    else if (flg == 1)
    {
        l = hgint_minus(res, a, l1, b, l2);
    }
    else
    {
        l = hgint_minus(res, b, l2, a, l1);
    }
    if (flg == -1)printf("-");
    for (i = l - 1; i >= 0; i--)
        printf("%d", res[i]);
    return 0;
}

作答提示

高精度模板题，没任何思维难度，倒序存储然后模拟竖式从个位开始算，然后注意借位。

别忘了先比较大小，以及过滤前导零。

这种题直接准备好板子带到考场上抄就行了。

J 2的次幂表示

题目大意

此题为洛谷原题（P1010）。访问链接：https://www.luogu.org/problem/P1010

样例输入

137

样例输出

2(2(2)+2+2(0))+2(2+2(0))+2(0)

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
void solve(int n)
{
    int i = 15;
    int flg = 0;
    while (i >= 0)
    {
        int base = (1 << i);
        if (n & base)
        {
            switch(i)
            {
            case 2:
                printf("%s2(2)", flg ? "+" : ""), flg = 1;
                break;
            case 1:
                printf("%s2",flg ? "+" : ""), flg = 1;
                break;
            case 0:
                printf("%s2(0)",flg ? "+" : ""), flg = 1;
                break;
            default:
                printf("%s2(", flg ? "+" : ""),flg = 1;
                solve(i);
                printf(")");
            }
        }
        i--;
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    solve(n);
    return 0;
}

作答提示

递归。