精确表达浮点数 - 编程之美2.6

http://hi.baidu.com/silverxinger/item/472f68e20a6581bb2f140ba4

在计算机中，使用float或者double来存储小数是不能得到精确值的。如果你希望得到精确计算结果，最好是用分数形式来表示小数。有限小数或者无限循环小数都可以转化为分数。比如：
0.9 = 9/10
0.333（3）= 1/3（括号中的数字表示是循环节）
当然一个小数可以用好几种分数形式来表示。如：
0.333（3）= 1/3 = 3/9
       给定一个有限小数或者无限循环小数，你能否以分母最小的分数形式来返回这个小数呢？如果输入为循环小数，循环节用括号标记出来。下面是一些可能的输入数据，如0.3、0.30、0.3（000）、0.3333（3333）、……

解法：

        拿到这样一个问题，我们往往会从最简单的情况入手，因为所有的小数都可以分解成一个整数和一个纯小数之和，不妨只考虑大于0，小于1的纯小数，且暂时不考虑分子和分母的约分，先设法将其表示为分数形式，然后再进行约分。题目中输入的小数，要么为有限小数X=0.a1a2…an，要么为无限循环小数X=0.a1a2…an（b1b2…bm），X表示式中的字母a1a2…an，b1b2…bm都是0~9的数字，括号部分（b1b2…bm）表示循环节，我们需要处理的就是以上两种情况。

        对于有限小数X=0.a1a2…an来说，这个问题比较简单，X就等于（a1a2…an）/10n。

        对于无限循环小数X=0.a1a2…an（b1b2…bm）来说，其复杂部分在于小数点后同时有非循环部分和循环部分，我们可以做如下的转换：

X= 0.a1a2…an（b1b2…bm）

10n* X= a1a2…an.（b1b2…bm）

10n* X= a1a2…an+0.（b1b2…bm）

X =（a1a2…an+0.（b1b2…bm））/10n

        对于整数部分a1a2…an，不需要做额外处理，只需要把小数部分转化为分数形式再加上这个整数即可。对于后面的无限循环部分，可以采用如下方式进行处理：

令Y=0. b1b2…bm，那么

10m *Y=b1b2…bm.（b1b2…bm）

10m *Y=b1b2…bm+0.（b1b2…bm）

10m *Y-Y=b1b2…bm

Y= b1b2…bm/（10m-1）

将Y代入前面的X的等式可得：

X=（a1a2…an+Y）/10n

=（a1a2…an+ b1b2…bm/（10m-1））/10n

=（（a1a2…an）*（10m-1）+（b1b2…bm））/（（10m-1）*10n）

         至此，便可以得到任意一个有限小数或无限循环小数的分数表示，但是此时分母未必是最简的，接下来的任务就是让分母最小，即对分子和分母进行约分，这个相对比较简单。对于任意一个分数A/B，可以简化为（A/Gcd（A, B））/（B/Gcd（A, B）），其中Gcd函数为求A和B的最大公约数，这就涉及本书中的算法（2.7节“最大公约数问题”），其中有很巧妙的解法，请读者阅读具体的章节，这里就不再赘述。

         综上所述，先求得小数的分数表示方式，再对其分子分母进行约分，便能够得到分母最小的分数表现形式。

例如，对于小数0.3（33），根据上述方法，可以转化为分数：

0.3（33）

=（3 *（102-1）+ 33）/（（102-1）*10）

=（3*99+33）/990 

= 1 / 3

 对于小数0. 285714（285714），我们也可以算出：

0. 285714（285714）

= （285714 *（106-1）+ 285714）/ （（106-1）*106） 

= （285714*999999 +285714）/ 999999000000

= 285714 / 999999

= 2/7

Code from http://www.2cto.com/kf/201403/285003.html

typedef pair<unsigned long,="" pair<unsigned="" unsigned="" long=""> > decimal_type;

 

unsigned long gcd(unsigned long x, unsigned long y)

{

    return (!y) ? x : gcd(y, x % y);

}

 

unsigned int num_cnt(unsigned long data)

{

    unsigned int cnt = 0;

    while(data) {

        data /= 10;

        ++cnt;

    }

    return cnt;

}

 

pair<unsigned long,="" unsigned="" long=""> transform_dot(decimal_type data)

{

    unsigned long numerator = 0, denominator = 0;

    unsigned long deci = 0, noncir = 0, cir = 0;

    deci = data.first;

    noncir = data.second.first;

    cir = data.second.second;

    if(cir == 0) {

        numerator = noncir;

        denominator = pow(10, num_cnt(noncir));

    }

    else {

        numerator = noncir * (pow(10, num_cnt(cir)) - 1) + cir;

        denominator = pow(10, num_cnt(noncir) + num_cnt(cir)) - pow(10, num_cnt(noncir));

    }

    unsigned long gcd_tmp = gcd(numerator, denominator);

    numerator /= gcd_tmp;

    denominator /= gcd_tmp;

    return make_pair(numerator, denominator);

}

 

decimal_type get_frac()

{

    unsigned long i = 0, j = 0, k = 0;

    char ch = 0;

    while(cin >> ch && ch != '.') {

        i = i * 10 + ch - '0';

    }

    while(cin >> ch && ch != '(') {

        j = j * 10 + ch -'0';

    }

    if(ch == '(') {

        while(cin >> ch && ch != ')') {

            k = k * 10 + ch -'0';

        }

    }

    return make_pair(i, make_pair(j, k));

}