计蒜客T1098:大整数加法(高精度加法详解)

比眉伴天荒 2023-02-27 13:32 19阅读 0赞

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。这篇博客来讲解一下高精度问题中的加法。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  引子
 *  高精度算法简介
 *  大数的存储方式
 *  高精度加法
 *  高精度加法模板
 *  大整数加法题目详解
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  样例输入
     *  样例输出
     *  解题代码

# 引子 #

相信大家都会做 [计算A+B][A_B]这道题目,这道题目就是让我们输出 A + B 的值，但是这道题目呢？[大整数加法][Link 1]`【本题题解请看本博客最后一部分】`同样是计算两个数的和，但是这两道题目的解法是完全不同的。如果我们还像之前一样这样写那么题目肯定会 WA 的：

#include<iostream>
    using namespace std;
    
    int main() { 
        int A, B;
        cin >> A >> B;
        cout << A + B << endl;
        return 0;
    }

以为第二个题目的数据范围是 `0 ~ 10^200` 如果直接用 int 来存储数字肯定会出现数据溢出的情况。下面详细的解释一下如何做大整数加法，即高精度加法。

# 高精度算法简介 #

>  高精度算法，属于处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，`高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。`对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， `用一个数组去表示一个数字`，这样这个数字就被称为是`高精度数`。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。  
>  在C/C++的计算中如果处理不好很容易出现`数据溢出`的情况。比如 int 型数据的范围为 `-2147483648 ~ +2147483647 (4 Bytes)` （更多数据范围请看 [char,short ,int ,long,long long,unsigned long long数据范围][char_short _int _long_long long_unsigned long long]）如果一个比这个数据范围还要大的数，那么我们就不能直接存储在 int 变量中，否则会出现数据溢出的问题。一旦出现数据溢出的情况首先会造成程序的计算结果不正确，更严重的情况会造成缓冲区溢出而受到黑客的攻击。一般我们做题目的时候题目都会提供数据范围，当给定的数据范围很大的时候我们一定要注意这个题目是不是高精度问题。比如在我之前的博客中就有一个这样的问题：[蓝桥杯练习系统 基础练习（vip试题）：BASIC-30 阶乘计算][_vip_BASIC-30] 。

# 大数的存储方式 #

对于数字我们人类的习惯是先写高位再写低位，但是在计算机中计算的时候如果我们也按照从高位到低位存储数字，那么在运算的过程中会产生一些不必要的麻烦。比如对齐数位问题、进位问题都不是特别好处理，对于我们写程序造成了不必要的麻烦。所以在数组中我们按照从低位到高位存储大数，即现存个位，再存十位，再存百位……。比如我们有一个数组 A ,那么A\[0\]存个位，A\[1\]存十位，A\[2\]存百位……以此类推。  
 由于高精度数都比较大，所以在存储的过程中我们一般先以将数字存到一个 string 类型的字符串中，然后将其每一位减去 ‘0’ 再存入到数组中（因为在计算机中每一个字符都有它的ASCII码，字符’0’ - ‘9’ 的 ASCII码的范围为 48 - 57，用字符串中每一个字符的ASCII码减去 ‘0’ 的ASCII码正好对应相应的数字）。这里我们使用C++的 vector容器 来存储大数，方便增加以及输出数字。  
![存储方式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]

# 高精度加法 #

其实高精度加法并没有我们想象中的那么难，实现的过程就是模拟了我们笔算加法的过程。`下面是具体的讲解，如果觉得写的繁琐可以直接看代码`。首先从个位开始相加，先将两个数组的第一位A\[0\]、B\[0\]相加即两个数的个位相加。使用一个变量 t 来存储相加的结果，将想相加之后的结果对 10 取模然后存到结果数组的个位上即C\[0\]上。然后再使 t 除以 10 如果两个个位相加超过了 10 那么除以 10 之后的到的就是进位的结果，然后依次相加十位百位等等，直到两个数组的数字都加完。这里我们需要设置一个 变量 i = 0 来记录遍历数组的下标，如果 i 还没有超过数组最大的下标那么就相加，否则就不想加。  
 比如 1234 + 56 我们会将其存储为 4321 + 65,4 + 6 = 10 ,10 % 10 = 0,10 / 10 = 1,所以我们将 0 存储在C\[0\]上，t = 1,然后再将 t + 3 = 4 , t + 5 = 9,此时9 % 10 = 9,9 / 10 = 0 , t = 0,这时56已经加完了，所以我们直接计算 t + 2 = 2, t = 0,t + 1 = 1,t = 0。所以最终 C\[0\] = 0,C\[1\] = 9,C\[2\] = 2,C\[3\] = 1，倒着输出数组C中的数字，即 1290 就是我们的答案了。  
 这里要特别注意：我们在 for 循环的结束条件还需要判断一下 t 是否为 0 因为即使最后将两个数加完了还可能存在进位的可能，如果不加这个条件那么最高位就会少个 1。

# 高精度加法模板 #

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() || t; i++) { 
            if (i < A.size()) t += A[i];
            if (i < B.size()) t += B[i];
            C.push_back(t % 10);
            t /= 10;
        }
        
        return C;
    }

# 大整数加法题目详解 #

## 题目描述 ##

求两个不超过 200200 位的非负整数的和。

## 输入格式 ##

有两行，每行是一个不超过 200200 位的非负整数，可能有多余的前导 00。

## 输出格式 ##

一行，即相加后的结果。结果里不能有多余的前导 00，即如果结果是 342342，那么就不能输出为 03420342。  
 输出时每行末尾的多余空格，不影响答案正确性

## 样例输入 ##

> 22222222222222222222  
> 33333333333333333333

## 样例输出 ##

> 55555555555555555555

## 解题代码 ##

#include<iostream>
    #include<vector>
    using namespace std;
    
    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() || t; i++) { 
            if (i < A.size()) t += A[i];
            if (i < B.size()) t += B[i];
            C.push_back(t % 10);
            t /= 10;
        }
        
        return C;
    }
    
    int main(){ 
        string a, b;
        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');
        
        vector<int> C = add(A, B);
        
        for (int i = C.size() - 1; i >= 0; i--) printf("%d",C[i]);
        
        return 0;
    }

`注意`：对于这个题目需要考虑前导零的情况，`比如199 + 000001 和 0 + 0两种特殊情况`，对于第一种我们只需要判断一下最后返回的数组C是否有前导零，如果有直接弹出即可;第二种结果就是0，但是我们不能将其弹出否则就输出为空，那么会有一组测试样例无法通过。所以`在去除前导零的时候需要先判断一下 C 的长度是否为 1 ，当长度为 1 的时候结果可能为 0 ，此时我们不需要弹出该 0 。`

--------------------

> 我是ACfun，感谢大家的支持！  
> ![嘿嘿嘿][20200717223443169.png]

[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[A_B]: https://nanti.jisuanke.com/t/T1001
[Link 1]: https://nanti.jisuanke.com/t/T1098
[char_short _int _long_long long_unsigned long long]: https://ac-fun.blog.csdn.net/article/details/104928574
[_vip_BASIC-30]: https://ac-fun.blog.csdn.net/article/details/105792627
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20230209/20f2c8c95c294d7a8a3e7959d87dc83c.png
[20200717223443169.png]: /images/20230209/04fa1a16c3ef41248b8df929fbe5ea44.png