[C++][题解]A+B Problem（高精）

[C++][题解]A+B Problem（高精） 题目 题目描述

高精度加法，相当于a+b problem，不用考虑负数.

输入格式

分两行输入。 a , b ≤ 1 0 500 a,b leq 10^{500} a,b≤10500

输出格式

输出只有一行，代表 a + b a+b a+b的值

题解

#include
#include
#include
using namespace std;
class BigInt{
private:
    string num; // 将大整数存在一个string对象里，整数的个位存在num[0]的位置。
public:
    BigInt(){num = "0";};
    const BigInt operator+ (const BigInt a)const;   // 重载加法运算符
    friend istream& operator>>(istream& in,BigInt &a);  // 重载左移运算符
    friend ostream& operator<<(ostream& out,const BigInt &a); // 重载右移运算符
};
const BigInt BigInt::operator+ (const BigInt a)const{
    BigInt s;
    string num;
    int k = 0;  // 进位
    int i;
    for(i = 0;i < this->num.length() && a.num.length();i++){
        int t = (this->num[i] - '0') + (a.num[i] - '0') + k;
        k = 0;
        if(t >= 10){
            k = 1;
            t %= 10;
        }
        num += t + '0';
    }
    for(;i < this->num.length();i++){
        int t = this->num[i] - '0' + k;
        k = 0;
        if(t >= 10){
            k = 1;
            t %= 10;
        }
        num += t + '0';
    }
    for(;i < a.num.length();i++){
        int t = a.num[i] - '0' + k;
        k = 0;
        if(t >= 10){
            k = 1;
            t %= 10;
        }
        num += t + '0';
    }
    if(k != 0)
        num += '1';
    s.num = num;
    return s;
}
istream& operator>>(istream& in,BigInt &a){
    in >> a.num;
    reverse(a.num.begin(),a.num.end());
    return in;
}
ostream& operator<<(ostream& out,const BigInt &a){
    string num(a.num);
    reverse(num.begin(),num.end());
    out << num;
    return out;
}

int main(){
    BigInt a,b; // 重载后的BigInt对象可以像int型变量一样直接进行加法运算和输入输出。
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

5至13行

class BigInt{
private:
    string num; // 将大整数存在一个string对象里，整数的个位存在num[0]的位置。
public:
    BigInt(){num = "0";};
    const BigInt operator+ (const BigInt a)const;   // 重载加法运算符
    friend istream& operator>>(istream& in,BigInt &a);  // 重载左移运算符
    friend ostream& operator<<(ostream& out,const BigInt &a); // 重载右移运算符
};

这里定义了一个大整数类。
因为本题的整数数值可能很大，使用int，long long都不能进行存储。
在C/C++的基本数据类型中，int类型的取值始终有上限。
所以在遇到这种需要超大整数的情况时，就得自己定义一个大整数类了。

因为本题需要对大整数进行输入输出和加法运算，所以分别重载了右移>>、左移<<、加法+运算符。

第9行

BigInt(){num = "0";};

这里是对BigInt类的构造函数的定义。
当在64行定义BigInt对象a、b时，

BigInt a,b;

a、b两个对象会分别调用该构造函数，将自身的数值初始化为0。

14至50行

const BigInt BigInt::operator+ (const BigInt a)const{
    BigInt s;
    string num;
    int k = 0;  // 进位
    int i;
    for(i = 0;i < this->num.length() && a.num.length();i++){
        int t = (this->num[i] - '0') + (a.num[i] - '0') + k;
        k = 0;
        if(t >= 10){
            k = 1;
            t %= 10;
        }
        num += t + '0';
    }
    for(;i < this->num.length();i++){
        int t = this->num[i] - '0' + k;
        k = 0;
        if(t >= 10){
            k = 1;
            t %= 10;
        }
        num += t + '0';
    }
    for(;i < a.num.length();i++){
        int t = a.num[i] - '0' + k;
        k = 0;
        if(t >= 10){
            k = 1;
            t %= 10;
        }
        num += t + '0';
    }
    if(k != 0)
        num += '1';
    s.num = num;
    return s;
}

这是BigInt类加法运算的具体定义。
主体为三个for循环。
因为两个数可能存在位数的差别，所以使用第一个for循环计算两个数都存在数位的部分，第二第三个循环计算高出的位数部分。
如图所示。

第51至61行

istream& operator>>(istream& in,BigInt &a){
    in >> a.num;
    reverse(a.num.begin(),a.num.end());
    return in;
}
ostream& operator<<(ostream& out,const BigInt &a){
    string num(a.num);
    reverse(num.begin(),num.end());
    out << num;
    return out;
}

这里要注意对位数进行反转，使得最低位位于下标0的位置（这样方便了加法时向高位进位）。

输入输出的重载虽然看着很复杂，但它的定义基本上都是同一个形式，熟练之后写起来并不难。
可参考资料：C++ 输入/输出运算符重载

补充

在python和java中，对于大整数问题有自己的优势。

python
python的整数类型无取值上限，所以不用自己定义类。
因此对于python，这道题3行代码即可解决：

a = int(input())
b = int(input())
print(a + b)

java
在java中，预置了一个BigInteger类，直接引入使用即可，同样不需要自己定义。

import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Main {
    public static void main(String []args) {
       Scanner s = new Scanner(System.in);
       BigInteger a = new BigInteger(s.next());
	   BigInteger b = new BigInteger(s.next());
	   s.close();
  	   System.out.print(a.add(b).toString());
    }
}

---

原创不易，感谢支持。