| ||||||||||
| 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