把两个不超过 100 位的非负整数按个位对齐倒序存进整型数组,逐位相加并传递进位,最后处理最高位进位并倒序输出。
OJ: roj
题目 ID: 2127
难度:普及-
标签:高精度模拟python
创建: 2026-10-08 07:45
更新: 2026-10-08 07:45
形式化题目
给定两个非负整数的十进制表示 0)。
即求
并输出
正解
思路
朴素做法及瓶颈。 直接 cin >> a >> b 用整型相加,C++ 里最大的定长类型 unsigned long long
上界约
关键观察:十进制加的每一位之间是解耦的,只通过进位耦合。
第
因为每一位的和至多是
对齐靠倒序。 人类书写时高位在左,而竖式要从最低位开始。把字符串倒序展开成整型数组后,
下标 zip_longest(fillvalue='0')),
不需要任何长度判断。
边界之一:最高位进位。 循环跑完长度较长的那个数之后,进位可能仍是
边界之二:前导零。 加法本身不会凭空制造前导零(除 0 而不是空行。
综合起来,整道题的算法就是
代码
Python 版(同样是竖式模拟,不借用 int 的大数能力,与 C++ 逐位对应):
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 07:45
# update_at: 2026-10-08 07:45
import sys
from itertools import zip_longest
def add_vertically(a: str, b: str) -> str:
"""竖式加法:低位对齐逐位相加、进位往上传递,返回无前导零的十进制结果。"""
carry = 0
low_to_high: list[str] = [] # 结果从低位往高位收集,输出前整体翻转
# 倒序遍历两个加数,短的那边补 '0',等价于 C++ 里全局数组初值全为 0
for x, y in zip_longest(reversed(a), reversed(b), fillvalue='0'):
carry, digit = divmod(int(x) + int(y) + carry, 10) # 本位留 digit,进位传高位
low_to_high.append(str(digit))
if carry:
low_to_high.append('1') # 最高位进位,如 99 + 1 = 100
return ''.join(reversed(low_to_high)).lstrip('0') or '0' # 去前导零,0 + 0 输出 0
def solve() -> None:
data = iter(sys.stdin.read().split())
a, b = next(data), next(data)
print(add_vertically(a, b))
if __name__ == "__main__":
solve()C++ 版:
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 07:45
* update_at: 2026-10-08 07:45
*/
// 一本通 2127《【例1.2】高精度加法》:两个不超过 100 位的非负整数求和。
// 做法:字符串读入 -> 倒序展开成数字(下标 0 是个位,天然按个位对齐)
// -> 逐位相加并传递进位 -> 处理最高位进位 -> 倒序输出。
// 位数上限 100,加上最高位进位共 101 位,数组开到 105 留余量。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXLEN = 105; // 位数上限 100 + 最高位进位 1 + 余量
int a[MAXLEN]; // a[i] = 第一个加数第 i 位(权重 10^i),全局默认 0 使不等长自动对齐
int b[MAXLEN]; // b[i] = 第二个加数第 i 位
int c[MAXLEN]; // c[i] = 和的第 i 位
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s1, s2;
if (!(cin >> s1 >> s2)) return 0; // 按 token 读入,可容忍行尾空白
int len1 = s1.length();
int len2 = s2.length();
// 倒序展开:最低位落在下标 0,两个加数即使位数不同也自动按个位对齐
for (int i = 0; i < len1; i++) a[i] = s1[len1 - 1 - i] - '0';
for (int i = 0; i < len2; i++) b[i] = s2[len2 - 1 - i] - '0';
int len = max(len1, len2);
int carry = 0; // 进位,每一位上只可能是 0 或 1
for (int i = 0; i < len; i++) {
int sum = a[i] + b[i] + carry; // 短的那边高位是 0,不需要额外判断
c[i] = sum % 10; // 本位保留个位
carry = sum / 10; // 进位交给下一位
}
if (carry > 0) c[len++] = carry; // 最高位进位,如 99 + 1 = 100
// 去掉前导零(输入带前导零时会出现),结果至少保留一位,故 0 + 0 输出单个 0
while (len > 1 && c[len - 1] == 0) len--;
for (int i = len - 1; i >= 0; i--) cout << c[i];
cout << '\n';
return 0;
}复杂度
- 时间:
, 是结果的位数(100 位加数 + 最高位进位)。每轮循环是常数次加减与取模, 实测整个程序在 ms 量级(限时 1000 ms)。 - 空间:
,三个长度约 的全局整型数组加一个输入字符串,占用在 KB 级(限时 64 MB)。 - Python 侧:
main.py的算法与 C++ 完全同阶(),但逐位做 int()/divmod的常数比 C++ 大, 好在时完全无风险;若把 add_vertically换成print(int(a) + int(b))也是同一阶, 这里保留竖式写法是为了和题解正文的推导一一对应。
总结
- 大数的表示先于大数的运算:不能用一个整型装下,就退回"每位一个元素"的数组/字符串表示, 再用人类竖式的规则在数组上重定义加法。
- 倒序展开是通用技巧:让下标
代表个位,既省掉了右对齐的长度讨论,又让"进位往上传递"变成下标自增, 高精度加法、减法、乘法的低位对齐都靠它。 - 两个必须检查的边界:循环结束后仍为
的进位(补最高位),以及输入或结果里的前导零(规范化输出)。 - 语言差异:Python 的
int本身是高精度实现,int(a) + int(b)可直接过题; 但 C++ 必须手写竖式,本题的价值就在于把这套流程写清楚。
补充说明
- 本题素材源里带有数据生成脚本(
data.py),data/的 10 个点是自造的;题面属于"一本通"例题, 网上存在多个重建版本,出题意图与原书可能有细微差异(例如是否允许输入前导零、是否保证)。 本解按最保守的语义实现:允许前导零、允许全零、允许位数悬殊(如 100 位加 1 位), 这几种情况在 data/中分别对应「前导零/零值」「」「悬殊长度」三类点。 - 素材源
std.cpp与本解语义一致(倒序存位、逐位进位、补最高位、去前导零),差别只在实现细节: 它把缓冲开到位并把输出拼成一个字符串一次性写出。两版对 10 个真实点均给出相同结果。 - 本解对 10 个真实数据点全部通过(
check_sample.py),main.py与main.cpp逐点一致。