高精度加减乘除运算
高精度加减乘除
- 高精度
- 例题1：高精度加法
- 例题2，高精度减法
- 例题3，高精度乘法
- 例题4，高精度除法
高精度
主要分为以下四种情况
1，A + B，其中 A 和 B 的位数都是 大概为 10^6左右
2，A - B，其中 A 和 B 的位数都是 大概为 10^6左右
3，A * a，其中 A 位数小于等于10^6，a的数值小于等于10000
4，A / b，其中 A 位数小于等于10^6，a的数值小于等于10000
（A / B 较难，而且用的比较少，暂时不考虑）
注： A <= 10 和 length(A)<10 的区别：前者只能取 0-9，后者可以取 0-999999999
例题1：高精度加法
题目链接: 高精度加法.
题目分析及代码：
思路：
1，将数存放到数组中，其中，数组第一个元素存放个位数，以此类推
2，模拟加法
#include<iostream>
#include<vector>
using namespace std;//const int N = 1e6 + 10;//这里直接取大好几位，为了避免溢出.实际上这个程序没有用到N// C = A + B
vector<int> add(vector<int> &A, vector<int> &B) //这里采用引用是为了避免再次复制，节省时间和空间
{vector<int> C;int t = 0;//表示进位for(int i = 0; i < A.size() || i < B.size(); i ++){if(i < A.size()) t += A[i];if(i < B.size()) t += B[i];C.push_back(t % 10);//十进制加法规则，t 大于 10 时，取其余数，并且产生进位t /= 10;//下一次进位}if(t) C.push_back(1);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 = add(A, B);for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);return 0;
}
例题2，高精度减法
题目链接: 高精度减法.
减法模拟：假设 A 有四位，B 有三位A3 A2 A1 A0
- B2 B1 B0
————————————————
减的过程中，假如 A0 < B0，我们需要向前一位借一位，假设借位为 t
每一位相减时对应以下两种情况：
Ai >= Bi : Ai - Bi - t
Ai < Bi : Ai + 10 - Bi - t
此外，如果 A < B，交换 A,B，结果加 - 号
代码如下：
#include<iostream>
#include<vector>
using namespace std;//判断A与B大小， A >= B 时返回 true
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;
}// C = A - B
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;if(i < B.size()) t -= B[i];C.push_back((t+10)%10);//这里是将 A 大于 B 和 A 小于 B 两种情况合二为一if(t < 0) t = 1;else t = 0;}//还需处理一下这种情况，如 234 - 230 = 004，我们需要去掉高位的 0while(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');if(cmp(A,B)){auto C = sub(A, B);for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);}else{auto C = sub(B, A);printf("-");for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);}return 0;
}
例题3，高精度乘法
题目链接: 高精度加法.
这个和加法流程差不多，代码如下：
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>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();//有可能是 12345 * 0 这种情况，如果没有这一步，将得到 0000 这个答案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 --) printf("%d", C[i]);return 0;
}
例题4，高精度除法
题目链接: 高精度除法.
思路：
模拟除法运算：0 1 1 2 C3 C2 C1 C0|————————————— | ——————————————————11 | 1 2 3 4 b | A3 A2 A1 A0| 1 1 |—————————————— ______________________ 1 3 r = A3 最初的余数 C3 = A3 / b1 1 r' = A3 % b 余数变为 r' —————————————— ————————————————————————2 4 r' * 10 + A2 这是前两位的余数2 2 r'' = r' % b C2 = r' / b—————————————— ————————————————————————2 r'' * 10 + A1 前三位的余数r''' = r'' % 10 C1 = r'' / b之后也是这个规律。。。。。
代码如下~
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>using namespace std;// C = A / b, r 为余数
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());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;auto C = div(A, b, r);//本来在除法中，按照模拟思路，A高位在前保存可能方便计算，但是因为一般情况下一个运算里面还涉及到加，减，乘法，//为了运算统一不出差错，这里A，C仍然高位在后低位在前保存for(int i = C.size() - 1; i >= 0; i --) printf("%d",C[i]);// cout << endl;cout <<endl << r << endl;return 0;
}
高精度就先写这么多~
高精度加减乘除运算
高精度加减乘除
- 高精度
- 例题1：高精度加法
- 例题2，高精度减法
- 例题3，高精度乘法
- 例题4，高精度除法
高精度
主要分为以下四种情况
1，A + B，其中 A 和 B 的位数都是 大概为 10^6左右
2，A - B，其中 A 和 B 的位数都是 大概为 10^6左右
3，A * a，其中 A 位数小于等于10^6，a的数值小于等于10000
4，A / b，其中 A 位数小于等于10^6，a的数值小于等于10000
（A / B 较难，而且用的比较少，暂时不考虑）
注： A <= 10 和 length(A)<10 的区别：前者只能取 0-9，后者可以取 0-999999999
例题1：高精度加法
题目链接: 高精度加法.
题目分析及代码：
思路：
1，将数存放到数组中，其中，数组第一个元素存放个位数，以此类推
2，模拟加法
#include<iostream>
#include<vector>
using namespace std;//const int N = 1e6 + 10;//这里直接取大好几位，为了避免溢出.实际上这个程序没有用到N// C = A + B
vector<int> add(vector<int> &A, vector<int> &B) //这里采用引用是为了避免再次复制，节省时间和空间
{vector<int> C;int t = 0;//表示进位for(int i = 0; i < A.size() || i < B.size(); i ++){if(i < A.size()) t += A[i];if(i < B.size()) t += B[i];C.push_back(t % 10);//十进制加法规则，t 大于 10 时，取其余数，并且产生进位t /= 10;//下一次进位}if(t) C.push_back(1);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 = add(A, B);for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);return 0;
}
例题2，高精度减法
题目链接: 高精度减法.
减法模拟：假设 A 有四位，B 有三位A3 A2 A1 A0
- B2 B1 B0
————————————————
减的过程中，假如 A0 < B0，我们需要向前一位借一位，假设借位为 t
每一位相减时对应以下两种情况：
Ai >= Bi : Ai - Bi - t
Ai < Bi : Ai + 10 - Bi - t
此外，如果 A < B，交换 A,B，结果加 - 号
代码如下：
#include<iostream>
#include<vector>
using namespace std;//判断A与B大小， A >= B 时返回 true
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;
}// C = A - B
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;if(i < B.size()) t -= B[i];C.push_back((t+10)%10);//这里是将 A 大于 B 和 A 小于 B 两种情况合二为一if(t < 0) t = 1;else t = 0;}//还需处理一下这种情况，如 234 - 230 = 004，我们需要去掉高位的 0while(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');if(cmp(A,B)){auto C = sub(A, B);for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);}else{auto C = sub(B, A);printf("-");for(int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);}return 0;
}
例题3，高精度乘法
题目链接: 高精度加法.
这个和加法流程差不多，代码如下：
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>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();//有可能是 12345 * 0 这种情况，如果没有这一步，将得到 0000 这个答案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 --) printf("%d", C[i]);return 0;
}
例题4，高精度除法
题目链接: 高精度除法.
思路：
模拟除法运算：0 1 1 2 C3 C2 C1 C0|————————————— | ——————————————————11 | 1 2 3 4 b | A3 A2 A1 A0| 1 1 |—————————————— ______________________ 1 3 r = A3 最初的余数 C3 = A3 / b1 1 r' = A3 % b 余数变为 r' —————————————— ————————————————————————2 4 r' * 10 + A2 这是前两位的余数2 2 r'' = r' % b C2 = r' / b—————————————— ————————————————————————2 r'' * 10 + A1 前三位的余数r''' = r'' % 10 C1 = r'' / b之后也是这个规律。。。。。
代码如下~
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>using namespace std;// C = A / b, r 为余数
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());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;auto C = div(A, b, r);//本来在除法中，按照模拟思路，A高位在前保存可能方便计算，但是因为一般情况下一个运算里面还涉及到加，减，乘法，//为了运算统一不出差错，这里A，C仍然高位在后低位在前保存for(int i = C.size() - 1; i >= 0; i --) printf("%d",C[i]);// cout << endl;cout <<endl << r << endl;return 0;
}
高精度就先写这么多~
发布评论