有意义网站,网站制作公司司,高价做单网站,移动互联网开发作业目录 前言
1 题目描述
2 分析
2.1 关键代码
2.2 关键代码分析
3 代码 前言
详细的代码里面有自己的部分理解注释#xff0c;注意该博客内容实现的高精度-除-高精度是利用前面写的高精度-减-高精度实现的的时间复杂度是O#xff08;n^2#xff09;
1 题目描述
给定两…目录 前言
1 题目描述
2 分析
2.1 关键代码
2.2 关键代码分析
3 代码 前言
详细的代码里面有自己的部分理解注释注意该博客内容实现的高精度-除-高精度是利用前面写的高精度-减-高精度实现的的时间复杂度是On^2
1 题目描述
给定两个非负整数不含前导 0 AB请你计算 A/B 的商和余数。
输入格式
共两行第一行包含整数 A第二行包含整数 B。
输出格式
共两行第一行输出所求的商第二行输出所求余数。
数据范围
1≤A的长度≤100000, 1≤B的长度≤100000, B 一定不为 0
输入样例
9000000000000000000000000
2000000000000000000000000
输出样例
4
1000000000000000000000000
2 分析
要写的是两个大整数的除法,结合前面写过的模板,应该可以用 A * B 的高精度乘法配合 A B 的加法来实现,但是时间上肯定很高很高了(因为我不会FFT的高精度乘法)或者只用高精度的减法来实现,所以综合看来还是减法实现比较好
2.1 关键代码
//A / B C 是商r 是余数
vint div2(vint A, vint B, vint r) {vint C;if(!cmp(A,B)) {C.push_back(0);r A;return C;}int t 0;
// vint temp(A.size());vint temp;for(int i A.size() - 1; i 0; i -- ) {//相当于// i 2 1 0// 0 1 3, 这个地方的下标是 0 1 2, 和上面不一样 // _____// 9 /1 2 3// 0// -----// 1 2// 9// -----// 3 3// 2 7// -----// 6// temp 保存余数每次看作两个高精度数 temp 和 B 的减法// temp 值的低位在数组高方便处理否则去掉前导 0 和控制大小比较麻烦// 也可能是我没想明白大家可以改进改进// C [0,1,3] ,注意是高位在数组低位//存的是 [1,2] ,比较或者减法需要反过来temp.push_back(A[i]);//因为 temp 是值的高位在数组低位所以在比较前需要反转reverse(temp.begin(),temp.end());//反转之后注意有前导 0 比如 12123 / 12 不去掉会影响结果while(temp.size() 1 temp.back() 0) temp.pop_back();//如果 tmp 大于 B, 说明可以减, 否则不能减while(cmp(temp,B)) {//结果是值的低位在数组低位temp sub(temp,B);t;}//减完之后还需要把 tmp 反转回来, 因为 sub 返回的是值低位在数组低位reverse(temp.begin(),temp.end());//t 不会 10C.push_back(t);t 0;}//在上面把 temp 又变成值的高位在数组低位所以在返回前需要反转reverse(temp.begin(),temp.end());r temp;//因为 C [0,1,3] 因为数值的高位在数组低位 要保证统一需要反转reverse(C.begin(),C.end());//反转之后商 C 前几个位置可能会出现前导0, 需要去掉while(C.size() 1 C.back() 0) C.pop_back();return C;
}
2.2 关键代码分析
首先,在我的想法中,既然需要用减法实现,那就需要做替换,用哪两个数来做减法,答案肯定是用 A 的高位足够大时的那几位减掉 B 的值.
其次,此时 A 的这些高位肯定比 B 大,并且因为 B 是高精度数,所以此时 A 的足够大的高位,也就是余数必定也是高精度数,而且每次这个余数都要改变,需要用它来减掉 B ,这时候能够减的次数就是商 C 的值.然后重复前面的过程就行了.
最后,例子如 123 / 9, A [3,2,1], B [9],注意数值的低位在数组低位,计算过程是从高位开始算,正常除法也是这样, 刚开始 temp A2 [1],比 B 小,不做减法 t 0, C [0],然后 temp [1,2],因为需要统一计算,必须要反转,注意反转后需要去除前导 0 ,反转后 temp 为 [2,1] 比 B 大,循环减法,在这里面 t 9, 然后减法完成之后, t 1 就是商,再将 temp 反转,因为存放余数的时候,数值低位在数组高位方便处理,然后重复就可以了
3 代码
#includeiostream
#includevector
#includealgorithmusing namespace std;
typedef long long LL;
typedef vectorint vint;const int N 1e5 10;//A B
bool cmp(vint A, vint 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
vint sub(vint A,vint B) {vint C;int t 0;//调用前保证 A Bfor(int i 0; i A.size(); i ) {t A[i] - t;if(i B.size()) {t t - B[i];}C.push_back((t 10) % 10);if(t 0) t 1;else t 0;}//记得去除前导 0while(C.size() 1 C.back() 0) {C.pop_back();}return C;
}//A / B C 是商r 是余数
vint div2(vint A, vint B, vint r) {vint C;if(!cmp(A,B)) {C.push_back(0);r A;return C;}int t 0;
// vint temp(A.size());vint temp;for(int i A.size() - 1; i 0; i -- ) {//相当于// i 2 1 0// 0 1 3, 这个地方的下标是 0 1 2, 和上面不一样 // _____// 9 /1 2 3// 0// -----// 1 2// 9// -----// 3 3// 2 7// -----// 6// temp 保存余数每次看作两个高精度数 temp 和 B 的减法// temp 值的低位在数组高方便处理否则去掉前导 0 和控制大小比较麻烦// 也可能是我没想明白大家可以改进改进// C [0,1,3] ,注意是高位在数组低位//存的是 [1,2] ,比较或者减法需要反过来temp.push_back(A[i]);//因为 temp 是值的高位在数组低位所以在比较前需要反转reverse(temp.begin(),temp.end());//反转之后注意有前导 0 比如 12123 / 12 不去掉会影响结果while(temp.size() 1 temp.back() 0) temp.pop_back();//如果 tmp 大于 B, 说明可以减, 否则不能减while(cmp(temp,B)) {//结果是值的低位在数组低位temp sub(temp,B);t;}//减完之后还需要把 tmp 反转回来, 因为 sub 返回的是值低位在数组低位reverse(temp.begin(),temp.end());//t 不会 10C.push_back(t);t 0;}//在上面把 temp 又变成值的高位在数组低位所以在返回前需要反转reverse(temp.begin(),temp.end());r temp;//因为 C [0,1,3] 因为数值的高位在数组低位 要保证统一需要反转reverse(C.begin(),C.end());//反转之后商 C 前几个位置可能会出现前导0, 需要去掉while(C.size() 1 C.back() 0) C.pop_back();return C;
}int main() {string a,b;cinab;//a 123,b 12vint A,B;//A[6 , 5 , 4 , 3 , 2 , 1]因为可能需要进位个位放数组低位方便在数组高位加上进位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);}// vint C sub(A,B);
//
// for(int i C.size() - 1 ; i 0 ; i --) {
// coutC[i];
// }// if(b 0) {
// couterror;
// } else {vint r;vint C div2(A,B,r);for(int i C.size() - 1 ; i 0 ; i --) {coutC[i];}cout\n;for(int i r.size() - 1 ; i 0 ; i --) {coutr[i];}//cout\nr;
// }return 0;
}
