【4. 高精度加法】

# 高精度加法

思路：

• 大整数存储（用数组来存储，数组第0位，存低位，数组最后一位存高位），因为在进行加法运算时，通常会有进位，而在数组的最后一位，进位比较容易，而如果在数组开头进位的话，需要把整个数组移动一位。
• 数组的每一位存一位数字

步骤

1. 因为输入的数大于longlong了，所以就用string存放；
2. 将string里存的数逆序存入数组，这样模拟手工从右往左计算过程。
3. 循环（长的那个数组有多少个数，就循环多少次），两数相加，如果数>10，那就保留各位，十位加到下一个数中。
4. 因为数逆序存入所以要逆序输出。

举例

计算 12696 + 6666 = 22362

代码

#include <iostream>
using namespace std;

#include <vector>

const int N = 1e6 + 10;

                                                         //C = A + B;
vector<int> add (vector<int> &A, vector<int> &B)         //传引用就是为了防止拷贝，减少空间的浪费
{
    vector<int> C;
    int 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];
        C.push_back(t % 10);
        t /= 10;
    }
    
    if (t) C.push_back(1);
    return C;
}

 int main()
 {
     string a, b;                                        //因为数字位数比较多，用字符串进行存储
     vector<int> A, B;
     
     cin >> a >> b;                                      //a = '123456789';
     for (int i = a.size()- 1; i >= 0; i --) A.push_back(a[i] - '0'); // A = [9, 8, 7, 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);
     for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
     return 0;
     
 }

// 中间可以写成下面这种方式
vector<int> add (vector<int> &A, vector<int> &B)   //传引用就是为了防止拷贝，减少空间的浪费
{
   vector<int> C;
   int t = 0;    //进位
   
   if (A.size() < B.size()) return add(B, A)    //保证A始终是长度最长的那个
       
   for (int i = 0; i < A.size() ; i ++)
   {
       t += A[i];                              //此时无须在判断A的长度，因为A是最长的需要一直加
       if (i < B.size())  t += B[i];
       C.push_back(t % 10);
       t /= 10;
   }
   
   if (t) C.push_back(1);
   return C;
}