问题描述
p11809原题链接:UVaOJ 11809 - Floating-Point Numbers
相关说明:本题为《算法竞赛入门经典(第2版)》习题 3-12
解法一:暴力(可预处理)
对于输入给出的十进制的 $AeB$ 表示,其对应值为 $A \times 10^{B}$. 我们需要找到合适的 $0 \leq M \leq 9$ , $1 \leq R \leq 30$, 使得 $f(M) \times 2^{g(E)} = A \times 10^{B}$ 成立。由于二进制表示最大值时,其每位数字一定是 1, 比如 $0.111111111_{2} \times 2^{111111_{2}}$ 可以进一步发现对应的十进制表示规律:$f(M)= 1 - \frac {1}{2^{M+1}}$ 以及 $g(E)=2^{E} -1 $. 因此这题变成了爆搜 $M$ 和 $E$ 值,满足:
$$
\begin{aligned}
1 - \frac {1}{2^{M+1}} \times {\color{blue}2^{2^{E} -1}} &= A \times {\color{blue}10^{B}} \\
\log{(1 - \frac {1}{2^{M+1}})} + \log{2^{2^{E} -1}}& = \log{A} + \log{10^{B}} \\
\log{(1 - \frac {1}{2^{M+1}})} + \log{2} \times (2^{E} -1)& = \log{A} + {B} \\
\end{aligned}
$$
这题想要 AC, 需要注意以下几个可能导致 WA 的情况:
- 题目虽然限制了范围,但需要两边做取 log10 对数处理,防止计算蓝色部分过程中发生溢出;
- C++ 中的浮点数除了单精度浮点数 float ,还有双精度浮点数 double,精度范围不同;
- 比较浮点数时没有取到合适的 epsilon 值(通常是取太小了),导致 find 失败。
优化思路:此题可以提前打表,避免每次输入新样例都从 $M=0, E=1$ 的位置重新计算。但由于题目输入数据样例规模不大(不超过 300 行),这里就懒得做优化了。只能省掉计算的时间,比较还是需要的,某种意义上反而增加代码复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <bits/stdc++.h> using namespace std; int main() { const int DIGIT_NUM = 15; const double EPS = 1e-6; string line; while (cin >> line) { if (line == "0e0") break; double a = stod(line.substr(0, DIGIT_NUM + 2)); int b = stoi(line.substr(DIGIT_NUM + 3)); double log_f = log10(a) + b; bool find = false; for (int i = 0; i <= 9 && !find; i++) for (int j = 1; j <= 30 && !find; j++) { a = 1 - 1 / pow(2, i + 1), b = pow(2, j) - 1; double log_largest = log10(a) + log10(2) * b; if (fabs(log_largest - log_f) <= EPS) { cout << i << " " << j << endl; find = true; } } } return 0; } |
注意 Python 代码这里使用 isclose 比较精度时范围缩小到了 1e-12:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
from math import log10, pow, isclose DIGIT_NUM = 15 while True: line = input() if line == "0e0": break a = float(line[:DIGIT_NUM + 2]) b = int(line[DIGIT_NUM + 3:]) log_f = log10(a) + b find = False m = 0 while m <= 9 and not find: e = 1 while e <= 30 and not find: a, b = 1 - 1 / pow(2, m + 1), pow(2, e) - 1 log_largest = log10(a) + log10(2) * b if isclose(log_f, log_largest, rel_tol=1e-12): print(m, e) find = True e += 1 m += 1 |