GESP 5级客观题｜高精度运算｜课后作业

考试频率：高频。本卷共 3 题。

1. 要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为

   //假设a和b均为正数，且a表示的数比b大
   vector<int> minus(vector<int> a, vector<int> b) {
   	vector<int> c；
   	int len1 = a.size();
   	int len2 = b.size();
   	int i, t;
   	for (i = 0; i < len2; i++) {
   		if (a[i] < b[i]) { //借位
   			_____________ // 在此处填入代码
   			a[i] += 10;
   		}
   		t = a[i] - b[i];
   		c.push_back(t);
   	}
   	for (; i < len1; i++)
   		c.push_back(a[i]);
   	len3 = c.size();
   	while (c[len3 - 1] == 0) {//去除前导0
   		c.pop_back();
   		len3--;
   	}
   	return c;
   }
   

   {{ select(1) }}

• a[i + 1]--;
• a[i]--;
• b[i + 1]--;
• b[i]--;

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

vector<int> multiply(vector<int> &a, vector<int> &b)
{
    int m = - size(), n = - size();
    vector<int> c(m + n, 0);
    // 逐位相乘，逆序存储
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            c[i + j] += a[i] * b[j];
        }
    }

    // 处理进位
    int carry = 0;
    for (int k = 0; k < - size(); ++k)
    {
        ________________________________ // 在此处填入代码
            c[k] = temp % 10;
        carry = temp / 10;
    }

    while (- size() > 1 && - back() == 0)
        - pop_back();
    return c;
}

{{ select(2) }}

• int temp = c[k];
• int temp = c[k] + carry;
• int temp = c[k] - carry;
• int temp = c[k] * carry;

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

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.en = 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 = 1;
        q.d[0] = 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);
}

{{ select(3) }}

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