华中科技大学2018算法实验

#include<iostream> #include<algorithm> #include<sstream> #include<fstream> #include<string> using namespace std; //将string类型字符串变为整数 int strToint(string k) { int res; stringstream instr(k); instr >> res; return res; } //将int类型变为string string intTostr(int value) { string res; stringstream tostr; tostr << value; tostr >> res; return res; } void removePrezero(string &str) { //去掉前置0 if (str.length() == 1) return; int k = 0; //前置0的个数 for (int i = 0; i < str.length(); i++) { if (str.at(i) == '0') k++; else break; } if (k == str.length()) str = "0"; else str = str.substr(k); } //大数相加(不考虑前置0) string add(string x, string y) { string result = ""; //去掉前置0 removePrezero(x); removePrezero(y); //反转字符串方便相加 reverse(x.begin(), x.end()); reverse(y.begin(), y.end()); for (int i = 0, c = 0; c || i < max(y.length(), x.length()); i++) { int t = c; if (i < x.length()) t += (x.at(i) - '0'); if (i < y.length()) t += (y.at(i) - '0'); int s = t % 10; //本位和 result.insert(0, intTostr(s)); c = t / 10; //进位 } return result; } string sub(string &x, string &y) { string result = ""; removePrezero(x); removePrezero(y); int len_x = x.length(); int len_y = y.length(); int len_max = len_x > len_y ? len_x : len_y; //最大长度 int *tempresult = new int[len_max]; string sign; //结果的符号 if (len_x > len_y) { sign = "+"; } else if (len_x < len_y) { sign = "-"; } else { int i; for (i = 0; i < len_x; i++) { if (x.at(i) == y.at(i)) continue; else if (x.at(i) > y.at(i)) { sign = "+"; break; } else { sign = "-"; break; } } if (i == len_x) return "0"; } //翻转字符串便于操作 reverse(x.begin(), x.end()); reverse(y.begin(), y.end()); int q = 0; //若x>y，则直接相减，否则执行-(y-x) for (int i = 0; i < len_max; i++) { //超过有效位后，就置为0 int aint = i < len_x ? x.at(i) - '0' : 0; int bint = i < len_y ? y.at(i) - '0' : 0; if (sign.at(0) == '+') tempresult[q++] = aint - bint; else tempresult[q++] = bint - aint; } //对每一位进行减法操作后的结果进行处理 for (int i = 0; i < q; i++) { if (tempresult[i] < 0) { tempresult[i] += 10; tempresult[i + 1] -= 1; //有借位 } } //删除高位的0 q--; while (tempresult[q] == 0) q--; //将结果转换位string类型 for (int i = q; i >= 0; i--) result += intTostr(tempresult[i]); if (sign.at(0) == '-') return sign + result; delete[] tempresult; return result; } //添加前置0 void addPrezero(string &str, int zero_num) { for (int i = 0; i < zero_num; i++) str.insert(0, "0"); } //添加后置0 string addLastzero(string str, int zero_num) { string s = str; for (int i = 0; i < zero_num; i++) s += "0"; return s; } //计算x和y的乘积，重载后可以接收int类型和string类型 string multiply(string &x, string &y) { //预处理,将X和Y处理成位数相同的数，且增加位数为2的指数倍，这样便于递归计算 int init_len = 4; if (x.length() > 2 || y.length() > 2) { //长度大于2时，最小长度为4 if (x.length() >= y.length()) { while (init_len < x.length()) init_len *= 2; //计算处理的长度 //添加前置0 if (x.length() != init_len) addPrezero(x, init_len - x.length()); addPrezero(y, init_len - y.length()); } else { while (init_len < y.length()) init_len *= 2; //添加前置0 addPrezero(x, init_len - x.length()); if (y.length() != init_len) addPrezero(y, init_len - y.length()); } } if (x.length() == 1) addPrezero(x, 1); if (y.length() == 1) addPrezero(y, 1); int n = x.length(); string result; string a1, a0, b1, b0; if (n > 1) { a1 = x.substr(0, n / 2); a0 = x.substr(n / 2, n); b1 = y.substr(0, n / 2); b0 = y.substr(n / 2, n); } if (n == 2) { //长度为2时，结束递归 int x1 = strToint(a1); int x2 = strToint(a0); int y1 = strToint(b1); int y2 = strToint(b0); int z = (x1 * 10 + x2) * (y1 * 10 + y2); result = intTostr(z); } else { string c2 = multiply(a1, b1); string c0 = multiply(a0, b0); string temp_c1_1 = add(a0, a1); string temp_c1_2 = add(b1, b0); string temp_c1_3 = add(c2, c0); string temp_c1 = multiply(temp_c1_1, temp_c1_2); string c1 = sub(temp_c1, temp_c1_3); string s1 = addLastzero(c1, n / 2); string s2 = addLastzero(c2, n); result = add(add(s1, s2), c0); } return result; } int main() { string a; string b; string result; ifstream in_data("in.dat"); ofstream out_data("out.dat"); int group; unsigned int op; in_data >> group; for (int i = 0; i < group; i++) { in_data >> a >> b; in_data >> op; //先处理正负号 bool flag_x = false; bool flag_y = false; bool flag; if (a.at(0) == '-') { flag_x = true; a = a.substr(1); } if (b.at(0) == '-') { flag_y = true; b = b.substr(1); } switch (op) { case 1: if (!flag_x && !flag_y) //两个都是正数 { result = add(a, b); //a+b } else if (!flag_x && flag_y) { result = sub(a, b); //a+(-b) } else if (flag_x && !flag_y) { result = sub(b, a); //-a+b } else { //-(a+b) result = add(a, b); result = result.insert(0, "-"); } break; case 2: if (!flag_x && !flag_y) //两个操作数都是正数 result = sub(a, b); else if (!flag_x && flag_y) // a-(-b) result = add(a, b); else if (flag_x && !flag_y) //-a - b { result = add(a, b); result = result.insert(0, "-"); } else { //-a-(-b) = b - a result = sub(b, a); } break; case 3: if ((flag_x && flag_y) || (!flag_x && !flag_y)) flag = false; else flag = true; result = multiply(a, b); if (flag) { //结果为负数 result.insert(0, "-"); } } out_data << result << endl; } cout << "结束" << endl; return 0; }