#G111. GESP level5 C++ 高精度运算

GESP level5 C++ 高精度运算

GESP level5 - C++ 高精度运算

  1. 下面的代码片段用于将两个高精度整数进行相加。请在横线处填入( ),使其能正确实现相应功能。
string add(string num1, string num2) {
    string result;
    int carry = 0;
    int i = num1.size() - 1, j = num2.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int x = (i >= 0) ? num1[i--] - '0' : 0;
        int y = (j >= 0) ? num2[j--] - '0' : 0;
        int sum = x + y + carry;
        carry = sum / 10;
        // 在此处填入代码
        return result;
    }
}

{{ select(1) }}

  • result = to_string(sum % 10) + result
  • result = to_string(carry % 10) + result
  • result = to_string(sum / 10) + result
  • result = to_string(sum % 10 + carry) + result
  1. 下面的C++代码使用数组模拟整数加法,可以处理超出大整数范围的加法运算。横线处应填入代码是( )。
vector operator +(vector a, vector b) {
    vector c;
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        // 在此处填入代码
    }
    if (t) c.push_back(t);
    return c;
}

{{ select(2) }}

  • c.push_back(t % 10), t = t % 10
  • c.push_back(t / 10), t = t % 10
  • c.push_back(t / 10), t = t / 10
  • c.push_back(t % 10), t = t / 10
  1. 要实现一个高精度减法函数,则下面代码中加划线应该填写的代码为( )。
//假设a和b均为正数,且a表示的数比b大
vector minus(vector a, vector b) {
    vector 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  1) 
        c.pop_back();
    return c;
}

{{ select(3) }}

  • a[i + 1]--
  • a[i]--
  • b[i + 1]--
  • b[i]--
  1. 小杨编写了一个如下的高精度除法函数,则横线上应填写的代码为( )。
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]  1 && c.d[c.len-1] == 0) c.len--;
    return c;
}
// 高精度除法(a/b,返回商和余数)
pair div(BigInt a, BigInt b) {
    BigInt q, r; // q是商,r是余数
    if(compare(a, b) < 0) {
        // 如果a= 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];
            }
            // 在此处填入代码
            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(4) }}

  • r.d[0] = a.d[i]
  • r.d[i] = a.d[i]
  • r.d[i] = a.d[i]
  • r.d[0] = a.d[i]
  1. 下面关于高精度运算的说法错误的是( )? {{ select(5) }}
  • 高精度计算主要是用来处理大整数或需要保留多位小数的运算
  • 大整数除以小整数的处理的步骤可以是,将被除数和除数对齐,从左到右逐位尝试将除数乘以某个数,通过减法得到新的被除数,并累加商
  • 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
  • 高精度加法运算的关键在于逐位相加并处理进位
  1. 小杨编写了一个高精度减法函数:
vector highPrecisionSubtract(vector a, vector b) {
    vector result;
    int borrow = 0;
    for (int i = 0; i < a.size(); ++i) {
        int digitA = a[i];
        int digitB = i < b.size() ? b[i] : 0;
        int diff = digitA - digitB - borrow;
        if (diff  1 && result.back() == 0) {
        result.pop_back();
    }
    return result;
}

下面说法正确的是( )? {{ select(6) }}

  • 如果数组a表示的整数小于数组b表示的整数,代码会正确返回二者的差为负数
  • 代码假设输入数字是以倒序存储的,例如500存储为{0, 0, 5}
  • 代码的时间复杂度为O(a.size()+b.size())
  • 当减法结果为0时,结果数组仍然会存储很多个元素
  1. 小杨想实现两个大整数的高精度乘法,他编写了以下代码的框架,横线上应填写的代码为( )?
vector multiply(vector& a, vector& b) {
    int m = a.size(), n = b.size();
    vector 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  1 && c.back() == 0) c.pop_back();
    return c;
}

{{ select(7) }}

  • int temp = c[k]
  • int temp = c[k] + carry
  • int temp = c[k] - carry
  • int temp = c[k] * carry
  1. 在高精度运算中,以下关于数组存储方式的说法正确的是( )? {{ select(8) }}
  • 必须将高位存储在数组的前面
  • 必须将低位存储在数组的前面
  • 高位在前或低位在前都可以,但需要保持一致性
  • 存储方式不影响运算逻辑