高精度（一）---高精度加法和高精度减法

一、高精度算法的定义

用于处理那些超出计算机常规数据类型（如整数、浮点数）所能表示范围的数字的算法。

主要思想：采用数组存储数字，并模拟加减乘除运算。

下面用几个题目进行解释。（本篇先介绍高精度加法和高精度减法，乘法和除法下一篇再介绍）。

二、高精度加法

题目描述（该题目来源于洛谷）

思路

代码

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

//用于存储输入的数和结果 以及他们对应的长度
int a[N],b[N],c[N];
int la, lb, lc;

void add(int c[], int a[], int b[]){
//模拟加法过程—对应位置相加
for(int i = 0; i < lc; i++){
c[i] += a[i] + b[i];
//处理进位
c[i+1] = c[i] / 10;
//处理正确的数
c[i] = c[i] % 10;
}

//处理多一位的情况
if(c[lc] != 0 ){
lc++;
}
}

int main(){
//采用字符串读入两个数
string x,y;
cin>>x>>y;

la = x.size();
lb = y.size();
lc = max(la,lb);

//将每个数逆序放入数组中
for(int i = 0; i < la; i++){
a[la – i – 1] = x[i] – '0';
}
for(int i = 0; i < lb; i++){
b[lb – i – 1] = y[i] – '0';
}

//调用加法函数
add(c,a,b);

//输出结果
for(int i = lc – 1; i >= 0; i–){
cout<<c[i];
}
return 0;
}

三、高精度减法

题目描述（该题目来源于洛谷）

思路

代码

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N], b[N], c[N];
int la, lb, lc;

//比较函数
bool cmp(string& x,string& y){
//先比较长度
if(x.size() != y.size()) {
return x.size() < y.size();
}

return x < y;
}
//减法函数
void sub(int c[], int a[], int b[]){
//模拟减法过程
for(int i = 0; i < lc; i++){
c[i] += a[i] – b[i];
if(c[i] < 0){
//处理借位
c[i + 1] -= 1;
//处理正确的数
c[i] += 10;
}
}

//处理前导0
while(lc > 1 && c[lc – 1] == 0){
lc–;
}
}
int main(){

//输入两个数
string x,y;
cin>>x>>y;

//需要保证是大数 – 小数 ————如果x是小数就交换
//调用比较函数
bool flag = cmp(x,y);
if(flag){
cout<<"-";
swap(x,y);
}

la = x.size();
lb = y.size();
lc = max(la,lb);

//将每个数逆序放入数组中存储
for(int i = 0; i < la; i++){
a[la – i – 1] = x[i] – '0';
}
for(int i = 0; i < lb; i++){
b[lb – i – 1] = y[i] – '0';
}

//调用减法函数
sub(c,a,b);

//输出结果
for(int i = lc – 1; i >= 0; i–){
cout<<c[i];
}

return 0;
}