欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【高精度模拟】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;
}

如果有问题,欢迎大家指正!!!