发帖
雷达卡
一、高精度加法
示例1：A + B 问题
题目描述
实现高精度加法运算，即解决类似 a + b 的大数相加问题。 无需考虑负数情况。输入格式
- 输入包含两行； - 每行分别是一个非负整数 a 和 b，且满足 a, b ≤ 10500。输出格式
- 输出仅一行，表示 a + b 的结果。样例输入与输出 #1
输入 #1
1
1输出 #1
2样例输入与输出 #2
输入 #2
1001
9099输出 #2
10100说明与提示
- 对于 20% 的测试用例，0 ≤ a, b ≤ 109； - 对于另外 40% 的测试用例，0 ≤ a, b ≤ 1018。高精度加法解题思路
- 将两个操作数的每一位数字逆序存入数组中，便于从低位开始计算（模拟手写竖式加法的过程）；
- 逐位相加，并处理进位：当前位若超过9，则向高位进位。
参考代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string A, B;
int a[520] = {0}, b[520] = {0}, c[520] = {0};
cin >> A >> B;
int len = max(A.length(), B.length());
// 将字符串倒序转为数字数组（个位在前）
for (int i = A.length() - 1, j = 1; i >= 0; i--, j++)
a[j] = A[i] - '0';
for (int i = B.length() - 1, j = 1; i >= 0; i--, j++)
b[j] = B[i] - '0';
// 逐位相加并处理进位
for (int i = 1; i <= len; i++) {
c[i] += a[i] + b[i];
c[i+1] = c[i] / 10; // 进位
c[i] %= 10; // 当前位保留余数
}
if (c[len + 1] != 0) len++; // 若最高位有进位，则长度+1
// 倒序输出结果（恢复正常顺序）
for (int i = len; i >= 1; i--)
cout << c[i];
return 0;
}
二、高精度乘法
示例1：A × B 问题
题目描述
给定两个非负整数，求它们的乘积。输入格式
- 两行输入，每行一个非负整数。输出格式
- 输出一个非负整数，表示两数之积。样例输入与输出 #1
输入 #1
1
2输出 #1
2说明与提示
- 每个输入整数不超过 102000。高精度乘法解题思路
- 将两个数的每一位拆分后存储到数组中；
- 模仿竖式乘法过程进行计算；
- 关键规律：a[i] × b[j] 的结果应累加到结果数组的第 i+j1 位上；
- 最后统一处理所有进位，并去除前导零。
参考代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string A, B;
int a[5010] = {0}, b[5010] = {0}, c[5010] = {0};
cin >> A >> B;
int lena = A.length();
int lenb = B.length();
// 字符串倒序转为数字数组
for (int i = lena - 1; i >= 0; i--)
a[lena - i] = A[i] - '0';
for (int i = lenb - 1; i >= 0; i--)
b[lenb - i] = B[i] - '0';
// 执行乘法：a[i] * b[j] → c[i+j-1]
for (int i = 1; i <= lena; i++) {
for (int j = 1; j <= lenb; j++) {
c[i + j - 1] += a[i] * b[j];
}
}
int len = lena + lenb; // 结果最大可能长度
// 处理进位
for (int i = 1; i <= len; i++) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
// 删除前导零
while (len > 0 && !c[len])
len--;
// 输出结果（从高位到低位）
for (int i = max(1, len); i >= 1; i--)
cout << c[i];
return 0;
}
三、高精度乘法与加法结合应用
示例1：阶乘之和
题目描述
使用高精度方法计算以下表达式的值： S = 1! + 2! + 3! + + n!，其中 n ≤ 50。 其中!阶乘的定义为：n! = n × (n-1) × (n-2) × … × 1。例如，5! 的计算过程为 5 × 4 × 3 × 2 × 1，结果为 120。
题目要求根据输入的正整数 n，计算并输出其阶乘值 S。
输入格式
一个正整数 n。
输出格式
一个正整数 S，表示 n 的阶乘结果。
样例输入 #1
3样例输出 #1
9数据范围说明
对于全部的测试数据，满足 1 ≤ n ≤ 50。
解题思路
由于 n 最大可达 50，而 50! 是一个非常大的数值，远超普通整数类型（如 long long）的表示范围，因此需要使用高精度计算方法来处理。本题采用数组模拟高精度乘法与加法的方式逐步求解。
具体步骤如下：
- 使用数组 fact[] 存储当前阶乘值的每一位数字，fact_len 记录该数的位数。
- 从 1 到 n 循环，每次将当前阶乘值乘以下一个整数 i，实现方式为高精度乘法函数 mul()。
- 同时维护一个累加和 sum[]，用于存储 1! + 2! + … + n! 的结果（虽然题目只输出最终阶乘，但代码结构中包含此逻辑），通过 add() 函数完成高精度加法。
- 所有运算完成后，逆序输出 sum 数组中的每一位，即为最终结果。
详细实现已在参考代码中注释清楚，便于理解每一步操作的目的和原理。
参考代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 高精度乘法：计算 (x-1)! * x 并更新结果
void mul(int fact[], int& fact_len, int x)
{
int temp[66] = { 0 };
for (int i = 1; i <= fact_len; i++)
{
temp[i] += fact[i] * x;
}
int len = fact_len;
// 处理进位
for (int i = 1; i <= len; i++)
{
temp[i + 1] += temp[i] / 10;
temp[i] %= 10;
}
// 扩展位数
while (temp[len + 1] != 0)
{
len++;
temp[len + 1] += temp[len] / 10;
temp[len] %= 10;
}
for (int i = 1; i <= len; i++)
{
fact[i] = temp[i];
}
fact_len = len;
}
// 高精度加法：将当前阶乘加到总和中
void add(int sum[], int &sum_len, int fact[], int fact_len)
{
int len = max(fact_len, sum_len);
int temp[66] = { 0 };
for (int i = 1; i <= len; i++)
{
temp[i] += sum[i] + fact[i];
}
// 处理进位
for (int i = 1; i <= len; i++)
{
temp[i + 1] += temp[i] / 10;
temp[i] %= 10;
}
// 调整长度
while (sum[len + 1] != 0)
{
len++;
}
for (int i = 1; i <= len; i++)
{
sum[i] = temp[i];
}
sum_len = len;
}
int main()
{
int n = 0;
cin >> n;
int fact[66] = { 0 }; // 存储当前阶乘
int fact_len = 1; // 当前阶乘的位数
int sum[66] = { 0 }; // 存储阶乘和
int sum_len = 1; // 阶乘和的位数
fact[1] = 1; // 初始化 1! = 1
sum[1] = 0; // 初始化和为 0
for (int i = 1; i <= n; i++)
{
mul(fact, fact_len, i);
add(sum, sum_len, fact, fact_len);
}
// 逆序输出结果
for (int i = sum_len; i >= 1; i--)
{
cout << sum[i];
}
return 0;
}
在《深入浅出程序设计基础》这本书中，第三题存在一种更加奇特的解法。这种解法较为复杂，我个人理解起来有一定困难。1
1如果读者对此感兴趣，可以自行查阅相关资料以获得更详细的解释。
京公网安备 11010802022788号
