题目
题目描述
高精度加法,相当于a+b problem,不用考虑负数.
输入格式
分两行输入。
a
,
b
≤
1
0
500
a,b \leq 10^{500}
a,b≤10500
输出格式
输出只有一行,代表
a
+
b
a+b
a+b的值
题解
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
class BigInt{
private:
string num;
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;
cin >> a >> b;
cout << a + b << endl;
return 0;
}
5至13行
class BigInt{
private:
string num;
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());
}
}
原创不易,感谢支持。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)