Floating-Point Numbers, UVa - 11809

思路&实现

这道题首先的突破口在于，给出的十进制数过于巨大，不仅 long long 很难存下，而且就算存下来，处理成浮点数还是非常麻烦的。
所以，应当另寻出路。注意到数据范围中， $0 \leq M \leq 9$ ， $1 \leq E \leq 30$ , 总共只有 $10 \times 30 = 300$ 种组合，所以打一下表，再对于每组输入穷举配对就行了。
在具体实现上，易知进制转换的等式
$(2^{-1} + 2^{-2} + ... + 2^{-M-1}) \times 2^{2^E}= A \times 10^B$
也即：
$(1 - 2^{-M-1}) \times 2^{2^E}= A \times 10^B$
为方便起见，令 $m = 1 - 2^{-M-1}$ ， $e = 2^E$ ，则有：
$m \times 2^e= A \times 10^B$
这里在理论上已经可以直接进行计算了。但是，还有一个大问题：两边的数还是可能非常大。如果使用 BigInteger 来进行操作，则又掉入了开头的那个大坑。所以，需要一些变形。
对两边取以10为底的对数，即用函数 log10() <cmath> ，得到 $\log{m}+ e = \log{A} + B$
这时，就很容易进行计算了（注意！B仍然需要 long long 来存储）
正如这篇题解里面所说，在 $0 < A < 1$ 时，本题会变得复杂一些，考虑到官方数据没有这种情况，在此不讨论。
另外有一个非常非常神奇的坑。在我计算 $m$ 和 $e$ 的时候，一开始用的是 m = 1 - (1 >> (M+1)) 以及 e = (1 << E)，却没有结果输出，改用 pow() <cmath> 函数时就对了 $orz$
还有一个自己挖的坑，输入中有 $e$ ，所以直接用 scanf("%lfe%lf", ...) 输入会被认为是科学记数法 QAQ ，所以要用流输入来整一整这个输入格式。 $(tqlwsl)$

Code

废话到此为止，代码拍上：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <string>
using namespace std;

double A;
long long B;
double a[10 + 5][30 + 5];
long long b[10 + 5][30 + 5];
double eps = 1e-5;

int main() {
    for(int i = 0; i <= 9; i++) {
        for(int j = 1; j <= 30; j++) {
            double m = 1-pow(2, -i-1), e = pow(2, j)-1;
            double t = log10(m)+e*log10(2);
            b[i][j] = (long long)t; a[i][j] = t-b[i][j];
        }
    }
    string s;
    while(cin >> s) {
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == 'e') s[i] = ' ';
        }
        stringstream buff(s);
        buff >> A >> B;
        if(A == 0) break;
        A = log10(A); 
        for(int i = 0; i <= 9; i++) {
            for(int j = 1; j <= 30; j++) {
                if(B == b[i][j] && fabs(A-a[i][j]) < eps) {
                    printf("%d %d\n", i, j);
                }
            }
        }
    }
    return 0;
}

最后编辑于：2019.07.07 22:21:06

Floating-Point Numbers, UVa - 11809

思路&实现

Code

推荐阅读更多精彩内容