首页 › 题库 › GESP编程能力等级认证 › 3.1 高精度加法

GESP-C++五级 题库

共 7 道题 · 按题型筛选,点「查看答案」核对解析
章节 3.1 高精度加法 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.1 高精度加法

下面代码实现了对两个数组表示的正整数的高精度加法(数组低位在前),则横线上应填写( )。

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; 
}
A
c.push_back(carry / 10); 
carry %= 10;
B
c.push_back(carry % 10); 
carry /= 10;
C
c.push_back(carry % 10);

D
c.push_back(carry); 
carry /= 10
答案与解析
正确答案:B
遍历两个数组对应位置的元素,逐位相加并加上进位值,将当前位的结果存入新数组,进位值更新为和除以10的商。若遍历结束后仍有进位,则需继续处理进位,将其按位分解并依次存入结果数组,直到进位为零。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.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] < 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 = 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);
}
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;
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.1 高精度加法

小杨编写了一个如下的高精度乘法函数,则横线上应填写的代码为?( )

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) {
        ______________________ // 在此处填入代码
        c[k] = temp % 10;
        carry = temp / 10;
    }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}
A
int temp = c[k];
B
int temp = c[k] + carry;
C
int temp = c[k] - carry;
D
int temp = c[k] * carry;
答案与解析
正确答案:B

高精度乘法(大数乘法)通过 逐位相乘并处理进位 来实现。

选项B正确,temp 是当前位的值加上前一位的进位。

题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.1 高精度加法

小杨编写了一个如下的高精度减法函数:

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;
}

下面说法,正确的是( )。

A
如果数组 a 表示的整数小于 b 表示的整数,代码会正确返回二者的差为负数。
B
代码假设输入数字是以倒序存储的,例如 500 存储为 {0, 0, 5} 。
C
代码的时间复杂度为 O(a.size()+b.size())
D
当减法结果为 0 时,结果数组仍然会存储很多个元素 0。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.1 高精度加法

以下关于高精度运算的说法错误的是( )。

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

C选项,高精度的乘法,运算时间和两个整数的长度之和有关,两个长度分别为len1和len2的整数相乘,结果的长度至少为len1+len2。

题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 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;
}
A
a[i + 1]–;
B
a[i]–;
C
b[i + 1]–;
D
b[i]–;
答案与解析
正确答案:A

当a[i] < b[i] 时,表示当前位需要借位。a[i + 1]-- 将下一位a[i + 1] 的值减一,以便在当前位进行借位操作。

题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 3.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;
}
A
result = to_string(sum % 10) + result;
B
result = to_string(carry % 10) + result;
C
result = to_string(sum / 10) + result;
D
result = to_string(sum % 10 + carry) + result;
答案与解析
正确答案:A
这道题暂未补解析。
题目详情