[C++][题解]A+B Problem(高精)

[C++][题解]A+B Problem(高精),第1张

[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());
    }
}

原创不易,感谢支持。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://www.outofmemory.cn/zaji/5712530.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表(0条)

保存