解题思路
大整数如何存储?
大整数以数组的方式存上每一位,并且数组的第0位存大整数的个位。
大整数如何相加?
两个大整数用数组表示好后,每一组对应位相加,即A0 + B0,A1 + B1,…,同时设置进位为t,A0 + B0时进位t = 0,以此类推。结果Ci = (Ai + Bi + t)mod 10,进位t = (Ai + Bi + t)整除 10
高精度加法算法模板
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
// C = A + B
vector<int> add(vector<int> &A, vector<int> &B)
{
// 用数组表示的整数A加上用数组表示的整数B,返回一个用数组表示的整数C
vector<int> C; //定义答案
int t = 0; //定义进位为t,最开始进位为0
for (int i = 0; i < A.size() || i < B.size(); i ++ )
{
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
// 前两行代码执行完后,t里面存的就是(Ai + Bi + 上一位进位t)
C.push_back(t % 10); // 当前这一位应该是t模10
t /= 10; // 如果t ≥ 10,那么应该进位
}
if (t) C.push_back(1); //如果最高位还有进位的话,要在C的最后加上一个1
return C;
}
int main()
{
string a,b; //两个大整数以字符串方式读进来
vector<int> A, B;
cin >> a >> b; // a = "123456"
//因为要逆序存储,所以应该倒着读写;字母类型转换成数字类型,要减去'0'
for (int i = a.size() - 1; i >= 0; i-- ) A.push_back(a[i] - '0'); // A = [6, 5, 4, 3, 2, 1]
for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
auto C = add(A, B); // auto表示编译器会自己推断该变量是什么类型的
for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]); //逆序输出
return 0;
}