用字符串实现大数相乘
发布时间:2020-12-14 02:53:54 所属栏目:大数据 来源:网络整理
导读:? ? 题目:用字符串实现整数的大数相乘。输入不合法则返回空字符串。 ? ? string Multiplication_of_large_Numbers(string s1,string s2){if (s1.empty() || s2.empty())return "";int sign1=1,sign2=1,sign;if (s1[0] == '+'){sign1 = 1;s1 = s1.substr(1,s
? ? 题目:用字符串实现整数的大数相乘。输入不合法则返回空字符串。 ? ? string Multiplication_of_large_Numbers(string s1,string s2) { if (s1.empty() || s2.empty()) return ""; int sign1=1,sign2=1,sign; if (s1[0] == '+') { sign1 = 1; s1 = s1.substr(1,s1.size() - 1); } else if (s1[0] == '-') { sign1 = -1; s1 = s1.substr(1,s1.size() - 1); } if (s2[0] == '+') { sign2 = 1; s2 = s2.substr(1,s2.size() - 1); } else if (s2[0] == '-') { sign2 = -1; s2 = s2.substr(1,s2.size() - 1); } //判断输入是否合法 if (s1.empty() || s2.empty()) return ""; for (int i = 0; i < s1.size(); i++) { if (s1[i]>'9' || s1[i] < '0') return ""; } for (int i = 0; i < s2.size(); i++) { if (s2[i]>'9' || s2[i] < '0') return ""; } //记录最终结果的正负号 sign = sign1*sign2; string result(s1.size() + s2.size(),'0'); int pos_start = result.size() - 1;//标记一次运算中,result的起点 //开始运算 for (int i2 = s2.size() - 1; i2 >= 0; i2--) { if (s2[i2] == '0') { pos_start--;//不要忘了 continue; } int index = pos_start;//对应于result相应的下标 int carry = 0; for (int i1 = s1.size() - 1; i1 >= 0; i1--) { int tmp= (s1[i1] - '0')*(s2[i2] - '0') + carry + result[index]-'0'; result[index] = tmp%10 + '0'; carry = tmp / 10; index--; } //消除进位 while (carry) { result[index] = (result[index] - '0' + carry )%10+'0'; carry = (result[index] - '0' + carry ) / 10; index--; } pos_start--;//不要忘了 } //消除开头的“0” int i; for (i = 0; result[i] == '0'; i++); result = result.substr(i,result.size() - 1 - i + 1); //结果是0的时候 if (result.empty()) return "0"; //加上负号 if (sign < 0) result = "-" + result; return result; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |