算法简介
高精度算法是用于解决超出基本数据类型数据范围的整数间的加减乘除问题。
时间复杂度
O(n)
实现原理
高精度是模拟了竖式运算的过程。
以下的算法代码只适合如下情况：
- 高精度加法：两个大正整数相加
- 高精度减法：两个大整数相减
- 高精度乘法：大正整数 * int类型
- 高精度除法：大正整数 / int类型
1. 高精度加法
首先保证长度最长的数在前面，之后若遍历到较短的数首部是便不再考虑该数。
遍历较长数，对两数的该位置进行相加，用变量 t 表示进位。
最后若 t 还有进位，则加上。
string Add(string &a, string &b)
{
if(a.size() < b.size()) return Add(b, a);
int t = 0;
string c = "";
int la = a.size(), lb = b.size();
for (int i = la-1 , j = lb-1 ; i >= 0 ; i -- , j -- )
{
t = t + (a[i] - '0');
if(j >= 0) t = t + (b[j] - '0');
c = to_string(t % 10) + c;
t /= 10;
}
if(t) c = to_string(t) + c;
return c;
}
2. 高精度减法
高精度减法与加法思想类似，但是在开始时应比较两数，若被减数小，则需要输出负号。
同样用变量 t 表示借位，对每一位进行操作。
最后若得到的数有前导零，则需要去除前导零。
如：111111 - 111000
按照该算法会得到 000111,去除前导零得到111
bool cmp(string &a, string &b)
{
if(a.size() != b.size()) return a.size() > b.size();
for (int i = 0 ; i <= a.size() ; i ++ )
{
if(a[i] != b[i])
{
return a[i] > b[i];
}
}
return true;
}
string Sub(string &a, string &b)
{
int t = 0;
string c = "";
int la = a.size(),lb = b.size();
for (int i = la - 1, j = lb - 1 ; i >= 0 ; i --, j -- )
{
t = (a[i] - '0') - t;
if(j >= 0) t = t - (b[j] - '0');
c = to_string((t + 10) % 10) + c;
if(t < 0) t = 1;
else t = 0;
}
while(c.size() > 1 && c.front() == '0') c.erase(c.begin());
return c;
}
3. 高精度乘法
乘法与加法类似，区别在于加法的 t 在过程中不会超过 10，而乘法会超过，所以终止条件应加上 t == 0。
string Mul(string &a, int b)
{
int t = 0;
string c = "";
int la = a.size();
for (int i = la - 1 ; i >= 0 || t ; i -- )
{
if(i >= 0) t += (a[i] - '0') * b;
c = to_string(t % 10) + c;
t /= 10;
}
while(c.size() > 1 && c.front() == '0') c.erase(c.begin());
return c;
}
4. 高精度除法
高精度除法的思想是进行多次大整数部分数与除数相除，之后得到的商进行拼接即得到的答案。
string Div(string &a, int b, int &r)
{
r = 0;
string c = "";
int la = a.size();
for (int i = 0 ; i < la ; i ++ )
{
r = r * 10 + (a[i] - '0');
c += to_string(r / b);
r %= b;
}
while(c.size() > 1 && c.front() == '0') c.erase(c.begin());
return c;
}
算法实例
题目描述1
AC代码1
#include <bits/stdc++.h>
using namespace std;
string Add(string &a, string &b)
{
if(a.size() < b.size()) return Add(b, a);
int t = 0;
string res = "";
int la = a.size(), lb = b.size();
for (int i = la-1 , j = lb-1 ; i >= 0 ; i -- , j -- )
{
t = t + (a[i] - '0');
if(j >= 0) t = t + (b[j] - '0');
res = to_string(t % 10) + res;
t /= 10;
}
if(t) res = to_string(t) + res;
return res;
}
int main()
{
string a,b;
cin >> a >> b;
string c = Add(a, b);
cout << c << endl;
return 0;
}
题目描述2
AC代码2
#include <bits/stdc++.h>
using namespace std;
bool cmp(string &a, string &b)
{
if(a.size() != b.size()) return a.size() > b.size();
for (int i = 0 ; i <= a.size() ; i ++ )
{
if(a[i] != b[i])
{
return a[i] > b[i];
}
}
return true;
}
string Sub(string &a, string &b)
{
int t = 0;
string res = "";
int la = a.size(),lb = b.size();
for (int i = la - 1, j = lb - 1 ; i >= 0 ; i --, j -- )
{
t = (a[i] - '0') - t;
if(j >= 0) t = t - (b[j] - '0');
res = to_string((t + 10) % 10) + res;
if(t < 0) t = 1;
else t = 0;
}
while(res.size() > 1 && res.front() == '0') res.erase(res.begin());
return res;
}
int main()
{
string a,b;
cin >> a >> b;
string res;
if(cmp(a, b)) res = Sub(a, b);
else res = Sub(b, a), cout << "-";
cout << res << endl;
return 0;
}
题目描述3
AC代码3
#include <bits/stdc++.h>
using namespace std;
string Mul(string &a, int b)
{
int t = 0;
string c = "";
int la = a.size();
for (int i = la - 1 ; i >= 0 || t ; i -- )
{
if(i >= 0) t += (a[i] - '0') * b;
c = to_string(t % 10) + c;
t /= 10;
}
while(c.size() > 1 && c.front() == '0') c.erase(c.begin());
return c;
}
int main()
{
string a;
int b;
cin >> a >> b;
string c = Mul(a,b);
cout << c << endl;
return 0;
}
题目描述4
AC代码4
#include <bits/stdc++.h>
using namespace std;
string Div(string &a, int b, int &r)
{
r = 0;
string c = "";
int la = a.size();
for (int i = 0 ; i < la ; i ++ )
{
r = r * 10 + (a[i] - '0');
c += to_string(r / b);
r %= b;
}
while(c.size() > 1 && c.front() == '0') c.erase(c.begin());
return c;
}
int main()
{
string a;
int b;
cin >> a >> b;
int r;
string c = Div(a,b,r);
cout << c << endl << r << endl;
return 0;
}
参考
[1] Acwing 算法基础课