GESP 五级 · GESP 202506 C++ 五级 第 15 题

小杨编写了一个如下的高精度除法函数，则横线上应填写的代码为（ ）。

const int MAXN = 1005; // 最大位数
struct BigInt {
    int d[MAXN]; // 存储数字，d[0]是个位，d[1]是十位，...
    int len;     // 数字长度

    BigInt() {
        memset(d, 0, sizeof(d));
        len = 0;
    }
};

// 比较两个高精度数的大小
int compare(BigInt a, BigInt b) {
    if (a.len != b.len) return a.len > b.len ? 1 : -1;
    for (int i = a.len - 1; i >= 0; i--) {
        if (a.d[i] != b.d[i]) return a.d[i] > b.d[i] ? 1 : -1;
    }
    return 0;
}

// 高精度减法
BigInt sub(BigInt a, BigInt b) {
    BigInt c;
    for (int i = 0; i < a.len; i++) {
        c.d[i] += a.d[i] - b.d[i];
        if (c.d[i] < 0) {
            c.d[i] += 10;
            c.d[i+1]--;
        }
    }
    c.len = a.len;
    while (c.len > 1 && c.d[c.len-1] == 0) c.len--;
    return c;
}

// 高精度除法 (a/b，返回商和余数)
pair<BigInt, BigInt> div(BigInt a, BigInt b) {
    BigInt q, r; // q是商，r是余数

    if (compare(a, b) < 0) { // 如果 a < b，商为0，余数为a
        q.len = 0;
        r = a;
        return make_pair(q, r);
    }

    // 初始化余数r为a的前b.len位
    r.len = b.len;
    for (int i = a.len - 1; i >= a.len - b.len; i--) {
        r.d[i - (a.len - b.len)] = a.d[i];
    }

    // 逐位计算商
    for (int i = a.len - b.len; i >= 0; i--) {
        // 把下一位加入余数
        if (r.len == 1 || r.d[0] != 0) {
            for (int j = r.len; j > 0; j--) {
                r.d[j] = r.d[j-1];
            }
            _______________________________ // 横线处
        } else {
            r.d[0] = a.d[i];
            r.len = 1;
        }

        // 计算当前位的商
        while (compare(r, b) >= 0) {
            r = sub(r, b);
            q.d[i]++;
        }
    }

    // 确定商的长度
    q.len = a.len - b.len + 1;
    while (q.len > 1 && q.d[q.len-1] == 0) q.len--;

    // 处理余数前导零
    while (r.len > 1 && r.d[r.len-1] == 0) r.len--;

    return make_pair(q, r);
}

A.

r.d[0] = a.d[i];
r.len++;

B.

r.d[i] = a.d[i];
r.len++;

C.

r.d[i] = a.d[i];
r.len = 1;

D.

r.d[0] = a.d[i];
r.len = 1;

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】高精度除法｜余数左移补位｜数组索引操作

1. 🎯 考纲定位

GESP 五级 算法设计模块，考查高精度运算。命题人卡住绝大多数考生的弱点：对高精度余数 r 的低位补位逻辑不清楚。五级学生通常只会背高精度加减乘，除法里"把下一位加入余数"这一步，很多人会想当然地写错索引。