在计算机中,使用 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,那么
           m
        10 *Y=b1b2...bm.(b1b2...bm)
          m
     ⇒ 10 *Y=b1b2...bm+0.(b1b2...bm)
          m
     ⇒ 10 *Y-Y=b1b2...bm
                       m
     ⇒ Y= b1b2...bm /(10 -1)
    将 Y 代入前面的 X 的等式可得:
    X =(a1a2...an+Y)/10n
    =(a1a2...an+ b1b2...bm/(10m-1))/10n
                         m              m
    =((a1a2...an)*(10 -1)+ (b1b2...bm))/((10 -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