高精度小數乘法題,核心是對小數點的處理。
使用string類和bign類可以使代碼比較簡潔。
思路:輸入後進行預處理,把小數點和後面的0去掉。然後進行整數的高精度乘法,最後再按小數的形式進行輸出。
// UVa 748 Exponentiation
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 10000;
struct bign
{
int len, s[maxn];
bign()//構造函數
{
memset(s, 0, sizeof(s));
len = 1;
}
bign operator = (const char * num)//重載運算符=
{
len = strlen(num);
for (int i = 0; i < len; i++)
s[i] = num[len - i - 1] - '0';
return *this;
}
bign(const char * num){ *this = num; }//支援初始化操作
bign operator = (int num)
{
char s[maxn];
sprintf(s, "%d", num);//把num輸出到字元串s中
*this = s;
return *this;
}
bign(int num){ *this = num; }
string str() const //利用string類把字元串數組轉換為字元串,友善用<<,>>輸出
{
string res = "";
for (int i = 0; i < len; i++)
res = (char)(s[i] + '0') + res;
if (res == "") res = "0";
return res;
}
bign operator + (const bign& b) const//定義加法
{
bign c;
c.len = 0;
for (int i = 0, g = 0; g || i < max(len, b.len); i++)//要兩個數的位數都計算一便
{
int x = g;//g為其餘數
if (i < len) x += s[i];
if (i < b.len) x += b.s[i];
c.s[c.len++] = x % 10;
g = x / 10;
}
return c;
}
bign operator += (const bign& b)
{
*this = *this + b;
return *this;
}
void clean()//把0排除,得到真實的len
{
while (len > 1 && !s[len - 1])
len--;
}
bign operator - (const bign& b) const
{
bign c;
c.len = 0;
for (int i = 0, g = 0; i < len; i++)
{
int x = s[i] - g;//減去借1
if (i < b.len) x -= b.s[i];//上減下
if (x >= 0) g = 0;
else
{
g = 1;//x<0說明需要向前借1
x += 10;//将x變為正
}
c.s[c.len++] = x;
}
c.clean();//x可能為0
return c;
}
bign operator -= (const bign& b)
{
*this = *this - b;
return *this;
}
bign operator * (const bign& b) const
{
bign c;
c.len = len + b.len;//結果的位數最大為兩個因子位數之和
for (int i = 0; i < len; i++)
for (int j = 0; j < b.len; j++)
c.s[i + j] += s[i] * b.s[j];//對應位置的積的和,累加起來就是結果
for (int i = 0; i < c.len - 1; i++)
{
c.s[i + 1] += c.s[i] / 10;//進位的值
c.s[i] %= 10;//餘數位
}
c.clean();
return c;
}
bign operator *= (const bign& b)
{
*this = *this * b;
return *this;
}
//重載比較運算符
bool operator < (const bign& b) const
{
if (len != b.len)
return len < b.len;
for (int i = len - 1; i >= 0; i--)
if (s[i] != b.s[i])
return len < b.len;
return false;
}
bool operator >(const bign& b) const
{
return b < *this;
}
bool operator == (const bign& b) const
{
return !(b < *this) && !(b > *this);
}
bool operator != (const bign& b) const
{
return b < *this || b > *this;
}
bool operator <= (const bign& b) const
{
return !(b < *this);
}
bool operator >= (const bign& b) const
{
return !(b > *this);
}
};
//重載<<,>>,支援直接輸出bign對象
istream& operator >> (istream &in, bign& x)//
{
string s;
in >> s;
x = s.c_str();
return in;
}
ostream& operator << (ostream &out, const bign& x)
{
out << x.str();
return out;
}
int main()
{
//freopen("data.txt", "r", stdin);
string a, b;
int n;
while (cin >> a >> n)
{
int i = a.find('.');//找出小數點的位置
for(int i = a.length() - 1; i >= 0; i--)//除去後面的0
if(a[i] == '0')
a.erase(i);
else
break;
b = a.substr(0, i) + a.substr(i + 1);//把小數點去掉組成新的數
const char * str = b.c_str();//轉化為c字元串
bign num = str;//轉化為bign對象
bign product = str;
for(int j = 1; j < n; j++)//累乘
product *= num;
int dos = (b.length() - i) * n;//得到小數點到最後非零位的長度
string c = product.str();//把bign對象轉化為string對象
dos = c.length() - dos;//得到小數點的新位置
if(dos < 0)//說明沒有整數部分
{
printf(".");
for(int k = dos; k < 0; k++)//把缺少的前導0補充輸出
printf("0");
}
for(int j = 0; j < c.length(); j++)//輸出c
if(j == dos)
{
printf(".");
j--;//找到小數點的位置後要j--,使c繼續不間斷輸出
dos = -1;//防止無限循環,缺少這步會使條件一直成立。
}
else
cout << c[j];
cout << endl;
}
}