[基础算法](3)高精度
引言
高精度算法就是利用程序模拟我们小学学的 竖式算术法 利用 string 分别存储 两个大数 由于考虑进位问题 在 加法 、乘法 、减法的模拟算法都需要从前往后计算,所以需要转换为逆序vector,则 int [0] = a[a.size()]
高精度加法
模板题:791. 高精度加法 - AcWing题库
代码:
#include<iostream>
#include<vector>
using namespace std;
string a,b;
vector<int >A,B;
//高精度加法模板:
vector<int> add(vector<int>& A, vector<int>& B) {
vector<int> C;
int i,t;//t为进位
for (i = 0, t = 0; i < A.size(); i++) {
t = A[i] + t;
if (i < B.size()) t += B[i];//若B有 则加
C.push_back(t % 10);
t /= 10;
}
while (i < B.size()) C.push_back(B[i] + t % 10), t = (B[i] + t) / 10,i++;//处理B剩余的数
if(t) C.push_back(t);
return C;
}
int main(){
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];
return 0;
}
高精度减法
模板题:792. 高精度减法 - AcWing题库
代码:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//比较A和B
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;
}
//高精度减法模板
//由于保证了 A > B 恒成立,则有最高位相减时不会向前借位
vector<int> sub(vector<int>& A, vector<int>& B) {
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i++) {
t = A[i] - t;//计算这一位的值 : 被减数 - 减数 - 进位
if (i < B.size()) t -= B[i];//判断B在这一位是否有数字,若有,则减去
C.push_back((t + 10) % 10);//存储这一位的值,加上向前借位的值取个位
if (t < 0) t = 1;//若t原本小于0,则代表需要向前借位,则将其初始为1
else t = 0;//否则不需要借位,则为0
}
while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0
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;
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];
return 0;
}
高精度乘法
模板题:793. 高精度乘法 - AcWing题库
代码:
#include<iostream>
#include<vector>
using namespace std;
string a;
int b;
vector<int >A, B;
//高精度乘整数模板:
vector<int> mul(vector<int> &A, int b) {
vector<int> C;
int i, t;
for (i = 0, t = 0; i < A.size()||t; i++) {
if (i < A.size()) t = A[i] * b + t;//计算该位的值
C.push_back(t % 10);//存储该位
t /= 10;//处理进位
}
while (t) C.push_back(t % 10), t /= 10;//处理进位
while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0
return C;
}
int main() {
cin >> a >> b;
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];
return 0;
}
这里给出 [ 高精度 * 高精度 ] 的代码:此代码应用到北大OJ1001题目中,笔记入口:北大OJ求幂算法 - Null'Blog (nullcode.fun)
void chen(char a[], char b[])
{
int c[410] = { 0 };
int i, j, sum, k, k1;
k = 409;
k1 = 409;
for (i = strlen(a) - 1; i >= 0; i--)
{
for (j = strlen(b) - 1; j >= 0; j--, k--)
{
sum = (a[i] - '0') * (b[j] - '0') + c[k];
c[k - 1] = c[k - 1] + sum / 10;
c[k] = sum % 10;
}
k = --k1;
}
for (i = 0; i < 410; i++)
{
if (c[i] != 0)
{
break;
}
}
for (j = i, i = 0; j < 410; i++, j++)
{
b[i] = c[j] + '0';
}
b[i] = 0;
}
高精度除法
模板题:794. 高精度除法 - AcWing题库
代码:
#include<iostream>
#include<vector>
using namespace std;
string a;
vector<int> A;
int b;
vector<int> dev(vector<int>& A, int b) {
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i++) {
t = t * 10 + A[i];//上一位的余数加上这一位的数形成新的被除数
C.push_back(t / b);//除去除数
t %= b;//更新余数
}
reverse(C.begin(), C.end());//将答案反转过来 去除前导0
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main() {
cin >> a >> b;
for (int i = a.size(); i >= 0; i--) A.push_back(a[i] - '0');
auto C = dev(A, b);
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
return 0;
}