高精度算法

(1)高精度加法首先对字符串进行处理string a,b; cinab; vectorintA(a.size()); vectorintB(b.size()); for(int i0;ia.size();i)A.push_back(a[i]-0); for(int i 0;i.size();i)B.push_back(b[i]-0);转换为vector数组并倒转数字{//为什么1.在处理加法时如果顺序存储最高位就是A[0],如果最高位要进位需要在a[0]前加一个数显然会很麻烦(要移动数组每一位)换一种想法只需要将数字倒过来相加最高位在数组最末位进位时只需要在数组最后添加一个数显然大大提升了效率接下来处理高精度加法函数vectorint add(vectorint A,vectorint B){ vectorintC; int carry0;//处理进位 for(int i0;iA.size()||iB.size();i){ if(iA.size())carryA[i]; if(iB.size())carryB[i]; C.push_back(carry%10); carry/10; } if(carry!0)C.push_back(carry); return C; }将ab的每一位拿出来相加存储carry的个位数存入C数组即可假设从开始相加carry为0,此时a与b的个位数相加没进位直接存入carry/10;carry归零如果进位将carry个位数取出存入后carry/10;将进位存储在下一次加法的初始carry中即可完成进位最后输出总结#include bits/stdc.h using namespace std; // 高精度加法C A B vectorint add(vectorint A, vectorint B) { vectorint C; int carry 0; // 进位 for (int i 0; i A.size() || i B.size(); i) { if (i A.size()) carry A[i]; if (i B.size()) carry B[i]; C.push_back(carry % 10); carry / 10; } if (carry) C.push_back(carry); // 最后的进位 return C; } int main() { string a, b; cin a b; // 转换为vector低位在前 vectorint 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); vectorint C add(A, B); // 输出结果从高位到低位 for (int i C.size() - 1; i 0; i--) cout C[i]; cout \n; return 0; }(2)高精度减法第一步与加法相同存储数字进入数组即可string a, b; cin a b; vectorint 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);接下来写一个函数判断a,b大小再进行减法bool compare(string a, string b) { if (a.length() ! b.length()) return a.length() b.length(); return a b; }接下来我们写减法函数对于减法函数在这里我们只考虑ab的情况因为我们的vector数组不能存储负数对于ab的情况我们在主函数中分情况讨论ab时就交换计算b-a的情况然后再添加负号vectorint sub(vectorint A, vectorint B) { vectorint C; for (int i 0, t 0; i A.size(); i) { t A[i] - t; // 先减去上一位的借位 if (i B.size()) t - B[i]; // 再减去B[i] C.push_back((t 10) % 10); // 结果 t t 0 ? 1 : 0; // 如果t0需要借位 } // 去掉前导零 while (C.size() 1 C.back() 0) C.pop_back(); return C; }为什么要(t10)%10?:这是因为在减法的时候有两种情况这一位够减了对于10再%10没有影响而这一位不够减时加10再%10就是向前借一位再减前导零在减法时可能会出现减法后由原本的位数减为少一位的情况这时候就会产生前导零最后减法模板#include iostream #include vector using namespace std; bool cmp(vectorint A, vectorint 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要求 A B vectorint sub(vectorint A, vectorint B) { vectorint C; for (int i 0, t 0; i A.size(); i) { t A[i] - t; // 先减去上一位的借位 if (i B.size()) t - B[i]; // 再减去B[i] C.push_back((t 10) % 10); // 结果 t t 0 ? 1 : 0; // 如果t0需要借位 } // 去掉前导零 while (C.size() 1 C.back() 0) C.pop_back(); return C; } int main() { string a, b; vectorint A, B; cin a b; // 读取A倒序存储 for (int i a.length() - 1; i 0; i--) A.push_back(a[i] - 0); // 读取B倒序存储 for (int i b.length() - 1; i 0; i--) B.push_back(b[i] - 0); // 判断大小并计算 if (cmp(A, B)) { vectorint C sub(A, B); for (int i C.size() - 1; i 0; i--) cout C[i]; } else { cout -; vectorint C sub(B, A); for (int i C.size() - 1; i 0; i--) cout C[i]; } return 0; }(3)高精度乘法高精度乘法一般分两种一种高精度X低精度一种高精度X高精度1.高精度×低精度这种比较简单列出处理进位即可与前面几种类似#includeiostream #includevector using namespace std; vectorint multiply(const vectorintA,long long b) { vectorint C; long long t0; for(int i0;iA.size()||t;i) { if (i A.size()) t A[i] * b; C.push_back(t%10); t/10; } while(C.size()1C.back()0)C.pop_back(); return C; } int main(){ string a; long long b; cinab; vectorintA; for(int ia.size()-1;i0;i--)A.push_back(a[i]-0); vectorint ansmultiply(A,b); for(int ians.size()-1;i0;i--)coutans[i] ; return 0; }2.高精度×高精度这里有一个比较重要的地方:竖式乘法中A的第i位置乘以B的第j位得到的数字应该在第ij位置上其余基本与前几项相同不过要单独处理进位#includeiostream #includevector using namespace std; vectorint multiply(const vectorintA,const vectorintB) { vectorintC(A.size()B.size(),0); for(int i0;iA.size();i) { for (int j0;jB.size();j) { C[ij]A[i]*B[j]; } } int t0; for (int i0;iA.size()B.size();i) { tC[i]; C[i]t%10; t/10; } while (C.size()1C.back()0)C.pop_back(); return C; } int main() { string a,b; cinab; vectorintA; vectorintB; for (int ia.size()-1;i0;i--)A.push_back(a[i]-0); for (int ib.size()-1;i0;i--)B.push_back(b[i]-0); vectorintansmultiply(A,B); for (int ians.size()-1;i0;i--)coutans[i] ; return 0; }