UVa_11809 Floating Point Numbers

算法

UVa 11809 题目。

UVa 11809 Floating Point Numbers

浮点数的格式如下所示。如题所述一致，i 位长度存储尾数 m，$(0.5≤m<1.0)$，j 位长度存储阶数 e 。 　　 　　　　　　　　| M（m，i位长度） | E（e，j位长度） |</u>

故数值N可以表示为：$N=m×2^e$。其中$m=1-(1/2)^{i+1}$。$e=2^j-1$。另一方面，题目所给输入为科学计数法所表示的数值，其数值可以表示为$M=A×10^B$，$(1.0≤A<10)$。故可得如下等式：

　　　　　　　　　　　　　　$N=M$
　　　　　　　　　　　　$m×2^e = A×10^B$
　　　　　　　　$log{10}^{m} + e×log{10}^{2} = log_{10}^{A} + B$
　　　　　　　　　　　　　　　$K_1=K_2$

每一个ｉ可以唯一决定一个ｍ，每一个ｊ可以唯一决定一个ｅ，故每一对（ｉ，ｊ）可以唯一决定一对（ｍ，ｅ），从而可以唯一得出一个$K_1$。所以本题应该列表，枚举出所有的（ｉ，ｊ）的组合可能。对题目输入的数计算出$K_2$后进行查表，从而得出（ｉ，ｊ）。

AC代码如下（代码不算简洁，个人理解所写）：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

//#define DEBUG
double g_zero = 0.1;

struct Table {
    double value;
} g_table[10][31];

void init() 
{
    int i=0, j=0;
    int zero_cnt = 0;
    
    // 计算查找表
    for (i=0; i<10; i++) {
        for (j=1; j<31; j++) {
            double m = 1-pow(0.5, i+1);
            int e = pow(2,j)-1;
            g_table[i][j].value = log10(m)+e*log10(2);
        }
    }
#ifdef DEBUG
    printf("Table:\n");
    for (i=0; i<10; i++) {
        for (j=1; j<31; j++) {
            printf("  (%d,%d)：%.15f\n", i, j, g_table[i][j].value);
        }
    }
#endif
    
    // 计算表项的最小差值,用于浮点数比较。
    for (j=1; j<31; j++) {
        for (i=1; i<10; i++) {
            if (g_zero > g_table[i][j].value-g_table[i-1][j].value) {
                g_zero = g_table[i][j].value-g_table[i-1][j].value;
            }
        }
    }
    for (zero_cnt=0; (int)g_zero==0; zero_cnt++,g_zero*=10); 
    for (i=0,g_zero=1.0; i<zero_cnt; i++,g_zero*=0.1);
#ifdef DEBUG
    printf("ZERO: %lf\n", g_zero);
#endif
}

int solve(double m ,int e)
{
    int i = 0, j = 0;
    double k = log10(m)+e;
#ifdef DEBUG
    printf("Solve Case:\n  K Value: %.15f (m:%.15f, e:%d)\n", k, m, e);
#endif
    for (i=0; i<10; i++) {
        for (j=1; j<31; j++) {
            if (k-g_table[i][j].value<g_zero && 
                    k-g_table[i][j].value>-g_zero) {
                printf("%d %d\n", i,j);
#ifdef DEBUG
                printf("\n");
#endif
                return 0;
            }
        }
    }
#ifdef DEBUG
    printf("No solve\n\n");
#endif
}

int main(int argc, char **argv)
{
    init();
    char data[1024];
    char *ptr = NULL;
    double m;
    int e;

    while (scanf("%s", data) == 1) {
        ptr=data;
        while (!(*(ptr)=='\0'||*(ptr)=='e')) ptr++;
        if (*(ptr) == 'e')  *ptr++ = '\0';
        sscanf(data, "%lf", &m);
        sscanf(ptr, "%d", &e);
#ifdef DEBUG
        printf("INPUT:%.15f - %d\n", m, e);
#endif
        if (e==0 &&(-g_zero<m&&m<g_zero))
            break;
        solve(m,e);
    }
    return 0;
}