【高精度模拟】POJ 1001 Exponentiation
程序员文章站
2024-03-17 23:01:10
...
这段时间要沉迷刷题一段时间了,就让CSDN陪我一起吧!
一、题目大意
题目意思很简单,就是要你求一个小数幂次的高精度值。
二、题目思路以及AC代码
这种题,不得不说,虽然写高精度写的很爽,但需要考虑的情况真的是太多了。我尽量的总结一下,高精度方面就没什么可说的了。
首先,第一个要注意的问题是,虽然让你算的是小数的乘法,但你不要傻了吧唧的去做小数的高精度,因为小数的乘法其实就整数的乘法加一个小数点而已,只需要提前计算出小数点的位置,就可以只算整数的乘法了。
然后,就是一些需要注意的细节问题。
- 前导0和小数后面的0,不能存在
- 如果输出是纯小数,则整数部分没有数,不能有0
- 如果输出是纯整数,则不能有小数点和小数部分
- 注意0的幂次是0
- 在计算小数点的位置时,如果输出小数最后存在0,则要去除之后再计算,比如10.000,其实是一个整数,不能小数点后位数为0
目前关于这道题,也就想了那么多,其实我也是看完discuss才AC的,哎,有点费脑子,大家如果还是WA的话,可以去看看POJ的discuss,有一个大牛提供了很多测试用例。
下面给出AC代码,7ms(说实话,这道题看代码没有什么用,还是自己看discuss找错误比较实在)
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
struct BigNumber
{
int digits[1000];
int size;
void init() {
for (int i = 0; i < 1000; i++) {
digits[i] = 0;
}
size = 0;
}
void setup(string s) {
init();
int len = s.length();
for (int i = len - 1; i >= 0; i--) {
if (s[i] == '.') continue;
digits[size++] = s[i] - '0';
}
}
BigNumber operator + (BigNumber a) {
BigNumber c;
c.init();
int len = max(a.size, size);
int tmp, carry = 0;
for (int i = 0; i < len; i++) {
tmp = a.digits[i] + digits[i] + carry;
c.digits[c.size++] = tmp % 10;
carry = tmp / 10;
}
while (carry) {
c.digits[c.size++] = carry % 10;
carry /= 10;
}
return c;
}
BigNumber operator * (int x) {
BigNumber c;
c.init();
int tmp = 0;
int carry = 0;
for (int i = 0; i < size; i++) {
tmp = digits[i] * x + carry;
c.digits[c.size++] = tmp % 10;
carry = tmp / 10;
}
while (carry) {
c.digits[c.size++] = carry % 10;
carry /= 10;
}
return c;
}
BigNumber operator * (BigNumber a) {
BigNumber c;
c.init();
BigNumber tmp;
tmp.init();
for (int i = 0; i < size; i++) {
tmp = a * digits[i] + tmp;
c.digits[c.size++] = tmp.digits[0];
tmp.removeLowest();
}
while (!tmp.isZero()) {
c.digits[c.size++] = tmp.digits[0];
tmp.removeLowest();
}
return c;
}
bool isZero() {
for (int i = 0; i < size; i++) {
if (digits[i]) return false;
}
return true;
}
void removeLowest() {
for (int i = 1; i < size; i++) {
digits[i - 1] = digits[i];
}
digits[size - 1] = 0;
size--;
}
void print() {
bool flag = false;
for (int i = size - 1; i >= 0; i--) {
if (!flag && digits[i] == 0)
continue;
flag = true;
cout << digits[i];
}
cout << endl;
}
bool allZero(int i) {
for (; i >= 0; i--) {
if (digits[i]) return false;
}
return true;
}
};
int main()
{
string str;
int exp;
while (cin >> str >> exp) {
int point = 0;
int len = str.length();
bool f = false;
for (int i = len - 1; i >= 0; i--) {
if (str[i] == '.') {
f = true;
break;
}
point++;
}
point *= exp;
if (!f) point = 0;
BigNumber a;
a.setup(str);
if (a.isZero()) {
cout << 0 << endl;
continue;
}
BigNumber res;
res.setup("1");
for (int i = 0; i < exp; i++) {
res = res * a;
}
int size = res.size;
if (point >= size) {
cout << ".";
for (int i = 0; i < point - size; i++) {
cout << 0;
}
for (int i = size - 1; i >= 0; i--) {
if (res.digits[i] == 0 && res.allZero(i)) break;
cout << res.digits[i];
}
cout << endl;
}
else if (point == 0) {
res.print();
}
else {
bool flag = false;
int cnt = 0;
int i = size;
while (cnt < size - point) {
i--;
if (!flag && res.digits[i] == 0) continue;
flag = true;
cout << res.digits[i];
cnt++;
}
if (!res.allZero(i - 1)) {
cout << ".";
i--;
for (; i >= 0; i--) {
if (res.digits[i] == 0 && res.allZero(i)) break;
cout << res.digits[i];
}
}
cout << endl;
}
}
return 0;
}
如果有问题,欢迎大家指正!!!
上一篇: Lua程序设计第4版第8章课后练习答案
下一篇: Lua程序设计第4版第5章练习答案