高精度加法 分为两种情况:压位,不压位
高精度压位运算
压位和不压位的高精度计算存在三点不同点(以下提到的压位都是压4位):
(1)存储:不压位的话,vector或者数组中每个数据是0~9;压位以后,每个数据是0~9999。
(2)计算过程:不压位的话,除数和模数都是10;压位以后,除数和模数都是10000。
(3)输出:不压位的话,直接输出;压位的话,需要格式化输出,最高位直接输出即可,其他位都需要输出4位数字,不足的前面补零
高精度加法
从前往后 位数大的作为A,t存储进位
从前往后遍历整个C数组 C中存储t % 10的值 从低位开始
#include<bits/stdc++.h>
using namespace std;
vector <int> add(vector <int> &A,vector<int> &B)
{
if(A.size() < B.size()) add(B, A);//A的位数必须大于B的位数
vector<int> C;//存答案
int t = 0;//存储进位
for(int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if(t) C.push_back(t);
return C;
}
int main()
{
string a,b;
vector<int> A,B;
cin>> a >> b;
for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
for(int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
vector<int> c = add(A, B);
for(int i = c.size() - 1; i >= 0; i -- ) cout << c[i];
cout<<endl;
return 0;
}
压九位代码
#include <iostream>
#include <vector>
using namespace std;
const int base = 1000000000;
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % base);
t /= base;
}
if (t) C.push_back(t);
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
{
s += (a[i] - '0') * t;
j ++, t *= 10;
if (j == 9 || i == 0)
{
A.push_back(s);
s = j = 0;
t = 1;
}
}
for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
{
s += (b[i] - '0') * t;
j ++, t *= 10;
if (j == 9 || i == 0)
{
B.push_back(s);
s = j = 0;
t = 1;
}
}
auto C = add(A, B);
cout << C.back();
for (int i = C.size() - 2; i >= 0; i -- ) printf("%09d", C[i]);
cout << endl;
return 0;
}
高精度乘法拓展版本
高精度x低精度
同样从小到大遍历数组 进位存储每一位与低精度
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for(int i = 0; i < A.size() || t; i ++ )
{
if(i < A.size()) t += A[i] * b;//关键步骤
C.push_back(t % 10);
t /= 10;
}
while(C.size() > 1 && C.back() == 0) C.pop_back(); //去除前导零 否则会出现00000 的情况
return C;
}
int main()
{
string a;
int b;
cin >> a >> b;
vector<int> A;
for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
auto C = mul(A, b);
for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
cout << endl;
return 0;
}
高精度x高精度
从小到大遍历
#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int> &A, vector<int> &B)
{
vector<int> C(A.size() + B.size() + 7, 0);
for(int i = 0; i < A.size(); i ++ )
for(int j = 0; j < B.size(); j ++ )
C[i + j] += A[i] * B[j];
int t = 0;
for(int i = 0; i < C.size(); i ++ )
{
t += C[i];
C[i] = t % 10;
t /= 10;
}
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a, b;
cin >> a >> b;
vector<int> A, B;
for(int i = a.size() - 1; i >= 0 ; i -- ) A.push_back(a[i] - '0');
for(int i = b.size() - 1; i >= 0 ; i -- ) B.push_back(b[i] - '0');
auto C = mul(A, B);
for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
return 0;
}
高精度减法
需要先存在一个比较函数 如果AB位数不等则返回A位数大于B
如果AB位数相等 判断各个字符是否相等 不等则返回A[i] > B[i]
输出模10以后的数
#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A, vector<int> &B)
{
if(A.size() != B.size()) return A.size() > B.size();
for(int i = A.size() - 1; i >= 0; i -- )
if(A[i] != B[i]) return A[i] > B[i];
return true;
}
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
int t = 0;
for(int i = 0; i < A.size(); i ++ )
{
t = A[i] - t;//当借位为0 把其值赋为A[i]
if(i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a,b;
cin >> a >> b;
vector<int> A, B;
for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
for(int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
vector<int> C;
if(cmp(A, B)) C = sub(A, B);
else C = sub(B, A), cout << '-';
for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
cout << endl;
return 0;
}
高精度除法(有些许不同)
从后往前遍历 输出r/b的答案 r = r * 10 + A[i]
最后利用reverse函数 调换顺序
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for(int i = A.size() - 1; i >= 0; i --)
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());//之所以需要reverse 因为遍历是从后往前遍历的 先算高位
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin >> a >> b;
vector<int> A;
for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
int r = 0;
auto C = div(A, b ,r);
for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
cout << endl << r <<endl;
return 0;
}