Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
终于过了,贴个代码(c++)纪念下#include <string> #include <vector> #include <iostream> using namespace std; void TrimZero(string &s) { // head int i = 0; while (i < s.length()) { if (s[i] == '0') { i++; continue; } else { break; } } if (i != 0) { s.erase(0, i); } int j = s.find_first_of('.'); if (j != string::npos) { i = s.length() - 1; //tail while (i >= 0) { if (s[i] == '0') { i--; } else if (s[i] == '.') { i--; break; } else { break; } } if (i < (int)s.length()-1) { s.erase(s.begin() + (i + 1), s.end()); } } if (s.length() == 0) { s.append(1, '0'); } } // d1=d1+d2 void AddDoubleStr(string &d1, string &d2) { if (d1.length() == 0) { d1 = d2; return; } int carry = 0; int a, b, r; // 加数 int pos1 = d1.find_first_of('.'); if (pos1 == string::npos) { pos1 = d1.length(); } int pos2 = d2.find_first_of('.'); if (pos2 == string::npos) { pos2 = d2.length(); } int l1 = d1.length() - pos1; int l2 = d2.length() - pos2; int i1, i2; // index if (l1 < l2) { i1 = d1.length() - 1; i2 = pos2 + l1 - 1; } else { i2 = d2.length() - 1; i1 = pos1 + l2 - 1; } while ((i1 >= 0 && i2 >= 0) || carry > 0) { if (i1 >= 0) { if (d1[i1] == '.') { i1--; i2--; continue; } a = d1[i1] - '0'; } else { a = 0; } if (i2 >= 0) { b = d2[i2] - '0'; } else { b = 0; } r = (a + b + carry) % 10; carry = (a + b + carry) / 10; if (i1 >= 0) { d1[i1] = '0' + r; } else { d1.insert(0, 1, (char)('0' + r)); } if (i1 >= 0) { i1--; } if (i2 >= 0) { i2--; } } // d2 head if (i2 >= 0) { d1.insert(0, d2, 0, i2 + 1); } // d2 tail if (l2 > l1) { d1.insert(d1.end(), d2.begin() + pos2 + l1, d2.end()); } } // d2=d1*m*10^n void Multiply1(string &d1, string &d2, int m, int n) { int a,r; int i = d1.length() - 1; int j = 0; int carry = 0; while (i >= 0) { if (d1[i] == '.') { d2.insert(0, 1, '.'); j = d2.length(); i--; continue; } a = d1[i] - '0'; r = (a * m + carry) % 10; carry = (a * m + carry) / 10; d2.insert(0,1,(char)('0' + r)); i--; } if (carry > 0) { d2.insert(0, 1, (char)('0' + carry)); } int point_pos = d2.length() - j; if (n == 0) { TrimZero(d2); return; } // delete old point if (n != 0 && point_pos != d2.length()) { d2.erase(d2.begin() + point_pos); } int len = d2.length(); // add new point and zero point_pos += n; if (point_pos > len) { d2.insert(d2.end(), point_pos - len, '0'); } else if (point_pos >= 0 && point_pos < len) { d2.insert(point_pos, 1, '.'); } else if(point_pos < 0) { d2.insert(0, -point_pos, '0'); d2.insert(0, 1, '.'); } TrimZero(d2); } // r=d1*d2 void Multiply2(string &d1, string &d2, string &r) { string t; int point_pos = d2.find_first_of('.'); if (point_pos == string::npos) { point_pos = d2.length(); } for (int i = d2.length() - 1; i >= 0; i--) { if (d2[i] == '.' || d2[i] == '0') { continue; } if (i > point_pos) { Multiply1(d1, t, d2[i] - '0', point_pos - i); } else { Multiply1(d1, t, d2[i] - '0', point_pos - i-1); } //cout << r << " " << t << endl; AddDoubleStr(r, t); t.clear(); } } string& Pow(string &d1, int m, string &r) { r.clear(); if (m == 0) { r.append(1, '1'); return r; } r = d1; for (int i = 1; i < m; i++) { string t; Multiply2(r, d1, t); r = t; } TrimZero(r); return r; } int main() { string d1; int m; vector<string> sv; vector<int> iv; while (cin >> d1 >> m) { sv.push_back(d1); iv.push_back(m); } for (int i = 0; i < sv.size(); i++) { cout << Pow(sv[i], iv[i], d3) << endl; } system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator