C++ 算法考级专栏
🎨 视觉封面【GESP】C++五级练习题 luogu-P1303 A*B Problem | 高精度计算
GESP C++ 五级练习题,高精度计算考点应用。四、五级考生推荐练习。题目难度⭐⭐☆☆☆,洛谷难度等级普及−。
luogu-P1303 A*B Problem
题目要求
题目背景
高精度乘法模板题。
题目描述
给出两个非负整数,求它们的乘积。
输入格式
输入共两行,每行一个非负整数。
输出格式
输出一个非负整数表示乘积。
输入输出样例 #1
输入 #1
1
2输出 #1
2说明/提示
每个非负整数不超过 。
题目分析
这道题的核心考点是 “高精度计算”,具体来说是 “高精度乘法”。
1. 为什么需要高精度计算?
题目中给出的两个非负整数,每个数的长度最大可能达到 (即 2000 位数字)。这远远超出了 C++ 中内置的基础数据类型(如 long long 或 unsigned long long,最大仅能表示 19/20 位数字左右)所能存储的极限范围。因此,我们必须借助数组和字符串来模拟我们小学阶段学习的手算乘法过程。
2. 字符串的读取与逆序存储
为了读取超长整数,我们需要使用 std::string 类型来接收输入的由数字组成的字符串。在拿到字符串形式的数字后,需要将它们逐位转换成整型数字并存入数组 a 和 b 中。
这里有一个很关键的逻辑技巧:逆序存储。我们将数字的个位存入数组的第一个位置(索引为 ),十位存入按索引 ,百位存入索引 ,以此类推。
这样处理的好处在于,当我们在稍后计算相乘产生向上进位时,可以顺应数组下标递增的方向(即高位索引方向)去进行 +1,从而避开了由于长度延伸而引起的繁琐的整体向右平移操作。
3. 核心算法:模拟竖式乘法
高精度乘法的核心逻辑无非是双重循环来模拟竖式乘法:
让数字 中的每一位 a[i] 去乘以数字 中的每一位 b[j],乘积的结果应该累加到最终结果数组所在的第 位上:c[i + j] += a[i] * b[j]。
需要注意的是,经过上述计算后,此时数组 c 里的每一个元素可能都会大于 。在这个阶段,我们先不去处理进位,只是单纯进行对应位上的累加。等所有乘法过程结束后,再统一进行一次整体的向上进位即可。
4. 统一进位与前导零处理
乘法双重循环跑完之后,我们必须顺次遍历结果数组一轮以处理所有进位:
- 统一的高位进位:对于结果数组的每一位
c[i],利用逢十进一的原则,将它对 取整 (c[i] / 10) 累加到它的高一位c[i + 1]上,并将当前位自身进行对 取模 (c[i] % 10) 计算并保留余数。 - 处理前导零的剔除:两个数(分别有 位和 位)相乘,积的总位数最大也就是 位(比如 就是 4 位)。因此最终结果数组
c的最大索引位置必定在一个有界的长度内。然而真实的积总位数长度可能并不会达到 这么大,在结果的最高位往往会产生一些冗余的零(即“前导零”)。我们需要从可能的最大高位开始向下挨个检查,若遇到0则将其削去,直到最高有效位(且要注意一种特例:如果是计算结果数字本身为0时,至少需保留一位输出,不能把所有0都给削空了)。
最后,因为真实的答案数值顺序是反过来的(存放在结果数组里是个位保存在索引 ),所以在拼接输出时,只需按照从大到小的下标顺位依次遍历并将其转换为对应的字符拼接即可。
示例代码
#include <algorithm>
#include <iostream>
// 数组大小开到 10^6 + 5,题目要求乘数不超过 10^2000,数组足够大
const int N = 10e5 + 5;
// a 数组存放被乘数,b 数组存放乘数,c 数组存放乘积
int a[N], b[N], c[N];
// 高精度乘法函数,传入两个大整数字符串,返回它们的乘积字符串
std::string big_multi(std::string num1, std::string num2) {
std::string res = "";
int n = num1.size(), m = num2.size();
// 逆序将字符串 num1 的每一位数字存入数组 a
// 使得字符串末尾(个位)存放在 a[0],十位存放在 a[1],以此类推
for (int i = n - 1; i >= 0; i--) {
a[n - i - 1] = num1[i] - '0';
}
// 逆序将字符串 num2 的每一位数字存入数组 b,个位数对应 b[0]
for (int i = m - 1; i >= 0; i--) {
b[m - i - 1] = num2[i] - '0';
}
// 模拟竖式乘法运算的核心过程
// a 的第 i 位乘以 b 的第 j 位,乘积应该累加到 c 的第 i+j 位上
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
c[i + j] += a[i] * b[j];
}
}
// 两个数相乘,乘积的总位数最多为它们的位数之和 (n + m)
int len = n + m;
// 处理统一进位:遍历乘积数组 c,如果当前位满 10,则向高位进位
for (int i = 0; i < len; i++) {
if (c[i] >= 10) {
c[i + 1] += c[i] / 10; // 向前(高位)进位
c[i] %= 10; // 当前位保留余数(个数)
}
}
// 去除前导零:结果可能没有达到 n + m 位,除了数字 0
// 本身(至少保留一位),把最高位多余的 0 去掉
while (len > 1 && c[len - 1] == 0) {
len--;
}
// 从高位到低位,将计算完毕整数逆序拼接回字符串
for (int i = len - 1; i >= 0; i--) {
res += c[i] + '0';
}
return res;
}
int main() {
std::string a, b;
// 读入两个非常大的非负整数字符串
std::cin >> a >> b;
// 调用大整数乘法计算函数并输出结果
std::cout << big_multi(a, b) << std::endl;
return 0;
}所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP】C++五级考试大纲知识点梳理, (1) 初等数论
GESP C++五级官方考试大纲中,共有9条考点,本文针对第1条考点进行分析介绍。 (1)掌握初等数论相关知识的概念和应用,包括素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性等。 由于本人也是边学、边实验、边总结,且对考纲深度和广度的把...
【GESP】C++五级考试大纲知识点梳理, (2) 模拟高精度计算
GESP C++五级官方考试大纲中,共有9条考点,本文针对第2条考点进行分析介绍。 (2)掌握 C++数组模拟高精度加法、减法、乘法和除法的相关知识。 五级其他考点回顾: - 【GESP】C++五级考试大纲知识点梳理, (1) 初等数论 由于本人也是边学、边实验、边总结...
【GESP】C++五级考试大纲知识点梳理, (3-1) 链表-单链表
GESP C++五级官方考试大纲中,共有9条考点,本文针对第3条考点进行分析介绍。 (3)掌握链表的创建、插入、删除、遍历和反转操作,理解单链表、双链表、循环链表的区别。 由于内容比较多,且涉及到代码的编写和验证,本知识点将分单链表、双链表、循环链表3次进行介绍。 本人...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

