本文共 4157 字，大约阅读时间需要 13 分钟。
对于大数加法，减法和乘法都可以用模拟的方法来解决，对于除法(一直做减法)，要使用加法和减法。
/*Leetcode 43. Multiply StringsGiven two numbers represented as strings, return multiplication of the numbers as a string.Note:The numbers can be arbitrarily large and are non-negative.Converting the input string to integer is NOT allowed.You should NOT use internal library such as BigInteger.解题思路：模拟手算。第i位乘以第j位得到的是(i+j)位的数*/#include#include #include #include using namespace std;class Solution {public: string multiply(string num1, string num2) { //先要反转，把最低位放在0的位置 reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); int tmp = 0; string s(num1.length() + num2.length(), '0'); for (size_t i = 0; i < num1.length(); ++i) { for (size_t j = 0; j < num2.length(); ++j) { tmp = (num1[i] - '0') * (num2[j] - '0'); //tmp为i位*j位 //把进位加到i+j+1位上 s[i + j + 1] = s[i + j + 1] - '0' + (s[i + j] - '0' + tmp) / 10 + '0'; //非进位的部分留在i+j位上 s[i + j] = (s[i + j] - '0' + tmp) % 10 + '0'; } } //处理完成后反转 reverse(s.begin(), s.end()); //去掉前面的0 auto pos = s.find_first_not_of('0'); if (pos == string::npos) //为0的情况 return "0"; else return s.substr(pos); }};void TEST(){ Solution sol; string s1 = "123"; string s2 = "234"; cout << sol.multiply(s1, s2) << endl;}int main(){ TEST(); return 0;}
/*OpenJudge2737 大数除法输入两个数，第一个被除数，第二个为除数，不超过100位输出：商的整数部分*/#include#include #include #include using namespace std;string sub(string s1, string s2){ int flag = 0; if (s1.length() < s2.length() || ((s1.length() == s2.length()) && s1 < s2)) { flag = 1; string tmp = s1; s1 = s2; s2 = s1; } int i, j; for (i = s1.length() - 1, j = s2.length() - 1; i >= 0; i--, j--) { s1[i] = char(s1[i] - (j >= 0 ? s2[j]-'0' : 0)); if (s1[i] < '0') { --s1[i - 1]; s1[i] += 10; } } for (i = 0; i < s1.length(); ++i) { if (s1[i] != '0') break; } if (i == s1.length()) i = s1.length() - 1; s1 = s1.substr(i); if (flag) s1 = "-" + s1; return s1;}string add(string s1, string s2){ if (s1.length() < s2.length()) { string tmp = s1; s1 = s2; s2 = tmp; } int i, j; for (i = s1.length() - 1, j = s2.length() - 1; i >= 0; --i,--j) { s1[i] = char(s1[i] + (j >= 0 ? s2[j] - '0' : 0)); if (s1[i] - '0' >= 10) { s1[i] = (s1[i] - '0') % 10 + '0'; if (i) s1[i - 1]++; else s1 = "1" + s1; } } return s1;}string div(string s1, string s2){ string res = "0"; if (s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2)) { return "0"; } int i; int subLen = s1.size() - s2.size(); for (i = subLen; i >= 0; --i) { string s3(i, '0'); string s4 = s2 + s3; //这里做减法，直到s1比s4小 do { string tmp = sub(s1, s4); if (tmp[0] == '-') break; //不够除 else { s1 = tmp; res = add(res, ("1" + s3));//根据s3的位数来确定加的数 } } while (1); } return res;}//顺便把乘法写了string mul(string s1, string s2){ reverse(s1.begin(), s1.end()); reverse(s2.begin(), s2.end()); int tmp = 0; string s(s1.size() + s2.size(), '0'); for (int i = 0; i < s1.size(); ++i) { for (int j = 0; j < s2.size(); ++j) { tmp = (s1[i] - '0')*(s2[j] - '0'); //进位 s[i + j + 1] = s[i + j + 1] + (s[i + j] - '0' + tmp) / 10; //非进位 s[i + j] = (s[i + j] - '0' + tmp) % 10 + '0'; } } reverse(s.begin(), s.end()); int pos = s.find_first_not_of('0'); if (pos == -1) return "0"; else return s.substr(pos);}int main(){ string s1, s2; cin >> s1 >> s2; cout << div(s1, s2) << endl; return 0;}
转载地址：http://emmxb.baihongyu.com/