MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 11809 - Floating-Point Numbers
AOAPC II

UVaOJ 11809 - Floating-Point Numbers

Chai
2021-11-24 0:00:00在线评测阅读 338

问题描述

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 行),这里就懒得做优化了。只能省掉计算的时间,比较还是需要的,某种意义上反而增加代码复杂度。

C++
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:

Python
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

AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz