POJ 1001 Exponentiation 无限大数的指数乘法 题解
发布时间:2020-12-14 03:37:40 所属栏目:大数据 来源:网络整理
导读:POJ做的很好,本题就是要求一个无限位大的指数乘法结果。 要求基础:无限大数位相乘 额外要求:处理特殊情况的能力 -- 关键是考这个能力了。 所以本题的用例特别重要,再聪明的人也会疏忽某些用例的。 本题对程序健壮性的考查到达了变态级别了。 某人贴出的
POJ做的很好,本题就是要求一个无限位大的指数乘法结果。 要求基础:无限大数位相乘 额外要求:处理特殊情况的能力 -- 关键是考这个能力了。 所以本题的用例特别重要,再聪明的人也会疏忽某些用例的。 本题对程序健壮性的考查到达了变态级别了。 某人贴出的测试用例数据地址:?http://poj.org/showmessage?message_id=76017 有了这些用例,几下调试就过了。 我关键漏了的用例: 000.10 ?1 #include <stdio.h> #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; bool standardizeNumNoDot(string &s) { while (!s.empty() && '0' == s[0]) s.erase(s.begin()); if (s.empty()) s = "0";//防止n==1的时候,要输出0 bool notDot = true; for (unsigned i = 0; i < s.size() && notDot; i++) { if ('.' == s[i]) notDot = false; } if (notDot) return true; while (!s.empty() && '0' == s[s.size()-1]) s.erase(s.end()-1); if (!s.empty() && '.' == s[s.size()-1]) s.erase(s.end()-1); if ( s.empty() ) s = "0"; return false; } int handleDecimalPoint(string &s) { if (standardizeNumNoDot(s)) return 0; int fraction = 0; int j = 0; for (unsigned i = 0; i < s.size() ; i++) { if (fraction > 0) fraction++; if (s[i] != '.') s[j++] = s[i]; else fraction++; } s.erase(s.end()-1); return fraction - 1; } string mulStr(string a,string b) { if ("0" == a || "0" == b) return "0"; int ap = handleDecimalPoint(a); int bp = handleDecimalPoint(b); string ans(a.size()+b.size(),'0'); for (int i = a.size() - 1; i >= 0 ; i--) { int carry = 0; int an = a[i] - '0'; for (int j = b.size() - 1; j >= 0 ; j--) { int bn = b[j] - '0'; int sum = an * bn + carry + ans[i+j+1] - '0'; carry = sum / 10; ans[i+j+1] = sum % 10 + '0'; } if (carry) ans[i] += carry; } if (ap > 0 || bp > 0) ans.insert(ans.end() - ap - bp,'.'); standardizeNumNoDot(ans); return ans; } string sPow(string s,int n) { if (s.empty() || "0" == s) return "0";//为了程序的健壮性,一定要加上 if (0 == n) return "1"; if (1 == n) return s; string divideStr = sPow(s,n/2); divideStr = mulStr(divideStr,divideStr); if (n % 2) divideStr = mulStr(divideStr,s); return divideStr; } void Exponentiation() { string s; int n; while(cin>>s>>n) { standardizeNumNoDot(s);//当n==1的时候 cout<<sPow(s,n)<<endl; } } int main() { Exponentiation(); return 0; }本算法用时0MS,哈哈. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |