大数加法【算法解析、代码模板、思路简单清晰】

791. 高精度加法 - AcWing题库

算法解析

大数加法其实本质上就是模拟 小学我们学的加法运算 + 分治 的思想

我们将一个很大的数字，拆成一个数的加法——分治思想

如何存储

如果对于一个真正很大的数字来说，可能long long都不支持（最多支持19位数 ）

但是一般来说大数都是1000位起步的，所以我们不能简单的使用long long进行处理，而是将其放在一个数组内，然后通过将每一位拆分出来，进行相加。

存放顺序

因为加法中设计到 进位 问题，所以我们需要首先计算个位数的

当然，也可以换一个角度进行考虑。因为我们是使用数组存储的，若将相加的结果放在前面的话，那么每计算一次都需要将后面的内容往后移一位空出第一位

代码模板

#include<iostream>
#include<vector>

using namespace std ;

string a , b ;

vector<int> add(vector<int> &A , vector<int>& B){
    vector<int> C;
    int carry = 0;
    for(int i = 0 ; i < A.size() || i < B.size() ; i ++){
        if(i < A.size()) carry += A[i];
        if(i < B.size()) carry += B[i];
        C.push_back(carry % 10);
        carry /= 10;
      
    }
    if(carry != 0){
        C.push_back(carry );
    }
  
    return C;
  
}

int main(){
    vector<int >A , B;
  
    cin >> a >> b;
  
    for(int i = a.size() - 1 ; i >= 0 ; i -- ) A.push_back(a[i] - '0');
    for(int i = b.size() - 1 ; i >= 0 ; i -- ) B.push_back(b[i] - '0');
  
    auto C = add(A , B );
  
    for(int i = C.size() - 1 ; i >=  0 ;  i --){
        cout << C[i];
    }
  
    return 0;
}

代码模板中我们采用的是vector其实本质上就是一个数组，但是它比较方便的是可以直接通过push_back添加数字进入数组的。

比较妙的一点

在函数add中，定义一个变量carry。判断当前是否需要添加A数组或B数组，这里需要明白的一点就是，若是数字的位数不对（如199 + 1），那么将不会遍历内容为1的数组B

完成相加后，直接将carry变量 % 10 后直接放入C中

因为在前面我们是倒序输入的，这里我们顺序输入C，那么最后我们需要将倒序输出正确结果

为什么在函数参数那里需要使用&？
因为这样子，C++就会只传递地址，而不传递真正的数据。
通过地址一样的可以达到访问数据的效果，实现更好的时间效率