高精度加法(A+B问题)
A+B,作为算法竞赛中最难的一题(雾),总是吸引着广大程序员想尽一切算法想要去AC它:
这里提供一种高精度的做法:
#include <iostream>
#define maxn 10000000 + 5
using namespace std;
string in;
int a[maxn], b[maxn], c[maxn];//分别为两个加数、和
int l1, l2, l3;//三个数组的长度
void turn(string in, int a[], int &n){
int i = 0, tmp = false;
if(in[0] == '-') {i = 1; tmp = true;}//判断负数
n = in.size();
for(; i < n; i++){
a[n - i - 1] = in[i] - '0';
}//把输入数的最高位放在数组的最低位
if(tmp) for(int i = 0; i < n; i++)
a[i] = -a[i];//减一个数等于加这个数的相反数
}
void _add(){
l3 = max(l1, l2);//和的数组的长度
for(int i = 0; i < l3; i++){
c[i] = a[i] + b[i];
}//首先进行加法运算
for(int i = 0; i < l3; i++){
if(c[i] >= 10){
c[i + 1] += c[i] / 10;
c[i] %= 10;
}//正数运算时,考虑进位问题
if(c[i] < 0){
c[i + 1] -= c[i] / 10 + 1;
c[i] = 10 + c[i];
}//负数运算时,考虑退位问题
}
l3 = l3 + (c[l3] ? 1 : 0);//判断最高位是否进位
}
void print(int a[], int l){
int tmp = false;
for(int i = l - 1; i >= 0; i--){
if(!tmp && !a[i] && i) continue;
else tmp = true;
cout << a[i];
}
cout << endl;
}//倒过来输出
int main(){
ios::sync_with_stdio(false);
cin >> in; turn(in, a, l1);
cin >> in; turn(in, b, l2);//输入及初始化
_add();
print(c, l3);
return 0;
}
潇洒地结束~