何为高精度
- 一般情况下，我们约定，能用int或者long表示的数据视为单精度，否则为高精度
- 高精度问题一般出现在数据范围极大，运算一定会溢出的情况
- 运算会溢出，但题目却没给要求要取模，此时要换为高精度运算
高精度运算模板
本模板所有函数的设计均采用带返回值的形式，但并不一定适配所有情况。
1.高精度加法
- 传参规定：传入string，返回string
- 支持范围：非负整数
- 算法思想：字符串倒置相加再还原
- 算法复杂度：O(n)
- 例题：洛谷 P1601 A+B Problem（高精）
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int len = 505; // 数字长度
// 非负整数相加
string add(string a, string b)
{
// 存放答案
string ans = "";
// 用于存储数字
int na[len] = {0}, nb[len] = {0};
// 把数字倒过来存储在数组前端
int la = a.size(), lb = b.size();
for(int i = 0; i < la; i++) na[la-1-i] = a[i]-'0';
for(int i = 0; i < lb; i++) nb[lb-1-i] = b[i]-'0';
// 遍历数组相加
int lmax = la>lb ? la : lb;
for(int i = 0; i < lmax; i++)
{
na[i] += nb[i]; // 每位相加，结果存储在na
na[i+1] += na[i]/10; // 相加之后产生的进位加到上一位中
na[i] %= 10; // 取余数
}
// 处理最高位产生的进位
if(na[lmax]) lmax++;
// 反置获得结果
for(int i = lmax-1; i >= 0; i--) ans += na[i]+'0';
return ans;
}
int main()
{
string a, b;
while(cin >> a >> b) cout << add(a,b) << endl;
return 0;
}2.高精度减法
- 传参规定：传入string，返回string
- 支持范围：只限大的非负整数减小的非负整数
- 算法思想：倒置相减再还原
- 算法复杂度：O(n)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int len = 505; // 数字长度
//只限大的非负整数减小的非负整数
string sub(string a,string b)
{
// 存放答案
string ans = "";
// 用于存储数字
int na[len]={0},nb[len]={0};
// 把数字倒过来存储在数组前端
int la=a.size(),lb=b.size();
for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
// 遍历数组相减
int lmax=la>lb?la:lb;
for(int i=0;i<lmax;i++)
{
na[i]-=nb[i]; // 每位相减，结果存储在na
if(na[i]<0) na[i]+=10,na[i+1]--; // 借位操作
}
while(!na[--lmax]&&lmax>0) ;lmax++;
for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
return ans;
}
int main()
{
string a, b;
while(cin >> a >> b) cout << sub(a,b) << endl;
return 0;
}参考资料
版权属于：PCsky
本文链接：http://hyouka.club/index.php/archives/5/
转载时须注明出处及本声明