高精度运算（共 8 题）

单选题

1. 下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用 int 表示，则横线处应该填写（ ）。

   int main() {
       string s; int b; cin >> s >> b;
       vector<int> a;
       for (char c : s) a.push_back(c - '0');
       vector<int> c;
       long long rem = 0;
       for (int i = 0; i < a.size(); i++) {
           rem = rem * 10 + a[i];
           int q = rem / b;
           c.push_back(q);
           __________________;
       }
       // 输出商和余数
   }
   

   {{ select(1) }}

• rem /= b;
• rem %= b;
• rem = b;
• rem = q;

2. 下面的 C++ 代码使用数组模拟整数加法，可以处理超出大整数范围的加法运算。横线处应填入代码是（ ）。

   vector<int> operator+(vector<int> a, vector<int> b) {
       vector<int> 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;

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

   //假设a和b均为正数，且a表示的数比b大
   vector<int> minus(vector<int> a, vector<int> b) {
       vector<int> c;
       int len1 = a.size(), 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]);
       while (c.size() > 1 && c.back() == 0) c.pop_back();
       return c;
   }
   

   {{ select(3) }}

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

4. 以下关于高精度运算的说法错误的是（ ）。
   {{ select(4) }}

• 高精度计算主要是用来处理大整数或需要保留多位小数的运算。
• 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。
• 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
• 高精度加法运算的关键在于逐位相加并处理进位。

5. 小杨编写了一个如下的高精度减法函数，下面说法正确的是（ ）。

   vector<int> highPrecisionSubtract(vector<int> a, vector<int> b) {
       vector<int> 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 < 0) {
               diff += 10;
               borrow = 1;
           } else {
               borrow = 0;
           }
           result.push_back(diff);
       }
       while (result.size() > 1 && result.back() == 0) result.pop_back();
       return result;
   }
   

   {{ select(5) }}

• 如果数组 a 表示的整数小于 b 表示的整数，代码会正确返回二者的差为负数。
• 代码假设输入数字是以倒序存储的，例如 500 存储为 {0,0,5}。
• 代码的时间复杂度为 O(a.size() + b.size())
• 当减法结果为 0 时，结果数组仍然会存储很多个元素。

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

   vector<int> multiply(vector<int>& a, vector<int>& b) {
       int m = a.size(), n = b.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 < c.size(); ++k) {
           int temp = c[k] + carry;
           c[k] = temp % 10;
           carry = temp / 10;
       }
       while (c.size() > 1 && c.back() == 0) c.pop_back();
       return c;
   }
   

   {{ select(6) }}

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

7. 下面代码实现高精度加法，横线处应填写（ ）。

   vector<int> add(vector<int> a, vector<int> b) {
       vector<int> c;
       int carry = 0;
       for (int i = 0; i < a.size() || i < b.size(); i++) {
           if (i < a.size()) carry += a[i];
           if (i < b.size()) carry += b[i];
           __________________;
       }
       if (carry) c.push_back(carry);
       return c;
   }
   

   {{ select(7) }}

• c.push_back(carry / 10); carry %= 10;
• c.push_back(carry % 10); carry /= 10;
• c.push_back(carry % 10);
• c.push_back(carry); carry /= 10;

判断题

8. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
   {{ select(8) }}

• 正确
• 错误