#gj001. 高精度加法
高精度加法
高精度加法
题目描述
给定两个非负整数 A 和 B,它们的位数可能超过普通整数类型(如 int 或 long long)的表示范围。请使用高精度加法(Big Integer Addition) 计算 A + B 的值,并输出结果。
算法概念
高精度加法(大整数加法)是处理超过基本数据类型表示范围的整数运算的常用方法。其核心思想是将大整数按位存储在数组中,从最低位(个位)开始逐位相加,同时处理进位,最终得到精确的计算结果。该方法模拟了手工竖式加法的过程。
算法原理与步骤
- 字符串读入:将两个大整数以字符串形式读入,方便处理任意长度的数字。
- 逆序存储:将字符串中的数字字符转换为整数,并逆序存入整型数组(数组下标 0 对应个位,下标 1 对应十位,以此类推)。这样做使得从低位到高位的计算更加方便。
- 逐位相加:从低位到高位遍历两个数组,对应位相加并加上低位的进位值(初始进位为 0)。当前位的计算结果为 (a[i] + b[i] + carry) % 10,新的进位为 (a[i] + b[i] + carry) / 10。
- 处理最高位进位:遍历结束后,若进位不为 0,则需将进位作为新的最高位添加到结果数组中。
- 逆序输出:从最高位到最低位依次输出结果数组中的数字,即为最终的和。
输入格式
第一行一个非负整数 A(可能很大)。
第二行一个非负整数 B(可能很大)。
输出格式
一行,输出 A + B 的结果(不含前导零,除非结果为 0)。
输入输出样例
输入输出样例 #1
123456789
987654321
1111111110
输入输出样例 #2
999
1
1000
输入输出样例 #3
0
0
0
数据规模与约定
- A 和 B 均为非负整数,长度不超过 200 位。
- 结果长度不超过 201 位。
- 时间限制:1 秒
- 内存限制:256 MB
提示
代码提示:
char a[205], b[205]; // 存储输入的大整数(字符串形式)
cin >> a >> b;
int la = strlen(a), lb = strlen(b);
int a1[205] = {}, b1[205] = {}; // 逆序存储的整型数组
// 将 a 逆序存入 a1
for (int i = 0; i < la; i++) {
// TODO: a1[la - 1 - i] = a[i] - '0';
}
// 将 b 逆序存入 b1
for (int i = 0; i < lb; i++) {
}
int lc = max(la, lb); // 结果位数至少为较长的位数
int c1[205] = {}; // 存储结果
int carry = 0; // 进位
// 逐位相加
for (int i = 0; i < lc; i++) {
}
// 处理最高位进位
if (carry != 0) {
}
// 逆序输出结果
for (int i = ? ; i >= 0; i--) {
cout << c1[i];
}
运用提示:
高精度加法的核心是“模拟竖式加法”,注意进位处理。
数字存储数组要初始化为0,非常重要
字符转数字时,用 a[i] - '0' 或 a[i] - 48 均可。
逆序存储是为了方便从低位对齐,因为两个数的位数可能不同。
结果数组的大小应至少为 max(la, lb) + 1,以容纳可能的最高位进位。
输出时需跳过前导零,但本题输出结果不含前导零(除非结果为 0,此时输出单个 0)。
扩展思考:高精度加法是其他高精度运算(减法、乘法、除法)的基础,掌握其模板对后续学习大有裨益。