UVaOJ 11809 - Floating-Point Numbers

问题描述

原题链接：UVaOJ 11809 - Floating-Point Numbers

解法一：暴力（可预处理）

对于输入给出的十进制的 $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 行），这里就懒得做优化了。只能省掉计算的时间，比较还是需要的，某种意义上反而增加代码复杂度。

#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;
}

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

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

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

AOAPC II UVaOJ 字符串