算法练习专栏——高精度加法、减法、乘法、除法
前言
学了这么久的计算机，大家应该也留意到了一件事情，我们的电脑（以32位为例） 对于一个整数一般最大的支持的位数为32位，即使是C++中表示最大范围的int__ 128 __，也可以表示2^128^左右，但是还不可以进行四则运算。那我们现在如果有两个 千位数 （有几千个数字构成） 相加等操作，应该如何计算呢？
这就是我们本节需要介绍的问题（本节学习难度不高，但是需要有深刻的理解，否则非常容易忘却）
一、高精度加法（简单+）
给定两个正整数（不含前导 0），计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤100000
输入样例：
1 | |
输出样例：
1 | |
思路
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < algorithm>
#include < vector>
using namespace std;
const int N = 1e5 + 10;
int n;
vector< int> a, b;
vector< int> add(vector< int> A,vector< int> B) {
vector< int> C;
int c = 0;
for (int i = 0; i < A.size() || i < B.size(); i++) {
if (i < A.size()) c += A[i];
if (i < B.size()) c += B[i];
C.push_back(c % 10);
c /= 10;
}
if (c) {
C.push_back(c);
}
return C;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string s1, s2;
cin >> s1 >> s2;
for (int i = s1.size() - 1; i >= 0; i--) a.push_back(s1[i] - '0');
for (int i = s2.size() - 1; i >= 0; i--) b.push_back(s2[i] - '0');
auto C = add(a, b);
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
return 0;
}
二、高精度减法（简单+）
给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤10^5^
输入样例：
1 | |
输出样例：
1 | |
思路
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < algorithm>
#include < vector>
using namespace std;
const int N = 1e5 + 10;
vector< int> A, B;
bool check(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 c = 0;
for (int i = 0; i < A.size(); i++) {
c += A[i];
if (i < B.size()) c -= B[i];
C.push_back((c + 10) % 10);
if (c >= 0) c = 0;
else c = -1;
}
while (C.back() == 0 && C.size() > 1) C.pop_back();
return C;
}
int main()
{
string s1, s2;
cin >> s1 >> s2;
for (int i = s1.size() - 1; i >= 0; i--) A.push_back(s1[i] - '0');
for (int i = s2.size() - 1; i >= 0; i--) B.push_back(s2[i] - '0');
if (check(A,B)) {
auto C = sub(A, B);
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
} else {
auto C = sub(B, A);
cout << "-";
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
}
return 0;
}
三、高精度乘法（简单+）
给定两个非负整数（不含前导 00） A 和 B，请你计算 A×B 的值。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共一行，包含 A×B的值。
数据范围
1≤A的长度≤100000
0≤B≤100000
输入样例：
1 | |
输出样例：
1 | |
思路
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < algorithm>
#include < vector>
using namespace std;
const int N = 1e5 + 10;
int n;
vector< int> A;
vector< int> mul(vector< int> A,int b) {
vector< int> C;
int c = 0;
for (int i = 0; i < A.size(); i++) {
c += A[i] * b;
C.push_back(c % 10);
c /= 10;
}
if (c) {
C.push_back(c);
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
int b;
string a;
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;
}
四、高精度除法（简单+）
给定两个非负整数（不含前导 0） A,B，请你计算 A/B 的商和余数。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000
1≤B≤10000
B 一定不为 0
输入样例：
1 | |
输出样例：
1 | |
思路
代码
答案（请自己先思考一下再参考）
#include < iostream>
#include < algorithm>
#include < vector>
using namespace std;
const int N = 1e5 + 10;
int n;
vector< int> A;
vector< int> Div(vector< int> A,int b,int& d) {
vector< int> C;
int c = 0;
for (int i = A.size() - 1; i >= 0; i--) {
c = c * 10 + A[i];
C.push_back(c / b);
c = c % b;
}
d = c;
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
int d = 0;
auto C = Div(A, b, d);
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
cout << '\n' << d;
return 0;
}