精确表达浮点数.pdf

1、写书评，赢取编程之美- 微软技术 面试心得 精确表达浮点数 在计算机中，使用 float 或者 double 来存储小数是不能得到精确值的。如果 你希望得到精确计算结果， 最好是用分数形式来表示小数。 有限小数或者无限循 环小数都可以转化为分数。比如： 0.9 = 9/10 0.333（3）= 1/3 （括号中的数字表示是循环节） 当然一个小数可以用好几种分数形式来表示。如： 0.333（3）= 1/3 = 3/9 给定一个有限小数或者无限循环小数， 你能否以分母最小的分数形式来返回 这个小数呢？如果输入为循环小数， 循环节用括号标记出来。 下面是一些可能的 输入数据，如 0.3、0.30、0

2、.3（000）、0.3333（3333）、 写书评，赢取编程之美- 微软技术 面试心得 分析与解法 拿到这样一个问题， 我们往往会从最简单的情况入手， 因为所有的小数都可 以分解成一个整数和一个纯小数之和， 不妨只考虑大于 0，小 于 1 的纯小数， 且 暂时不考虑分子和分母的约分，先设法将其表示为分数形式，然后再进行约分。 题目中输入的小数，要么为有限小数 X=0.a 1 a 2 a n ，要么为无限循环小数 X=0.a 1 a 2 a n （b 1 b 2 b m ），X 表示式中的字母 a 1 a 2 a n ，b 1 b 2 b m 都是 09 的数 字，括号部分（b 1 b 2 b

3、m ）表示循环节，我们需要处理的就是以上两种情况。 对于有限小数 X=0.a 1 a 2 a n 来说， 这个问题比较简单，X 就等于 （a 1 a 2 a n ） /10 n 。 对于无限循环小数 X=0.a 1 a 2 a n （b 1 b 2 b m ）来说，其复杂部分在于小数点 后同时有非循环部分和循环部分，我们可以做如下的转换： X = 0.a 1 a 2 a n （b 1 b 2 b m ） 10 n * X= a 1 a 2 a n .（b 1 b 2 b m ） 10 n * X= a 1 a 2 a n +0. （b 1 b 2 b m ） X = （a 1 a 2 a n

4、+0. （b 1 b 2 b m ）/10 n对于整数部分 a 1 a 2 a n ， 不需要做额外处理， 只需要把小数部分转化为分数 形式再加上这个整数即可。 对于后面的无限循环部分， 可以采用如下方式进行处 理： 令 Y=0. b 1 b 2 b m ，那么 10 m*Y=b 1 b 2 b m .（b 1 b 2 b m ） 10 m*Y=b 1 b 2 b m +0. （b 1 b 2 b m ） 10 m*Y -Y=b 1 b 2 b m Y= b 1 b 2 b m / （10 m -1） 将 Y 代入前面的 X 的等式可得： X = （a 1 a 2 a n +Y ）/10 n

5、= （a 1 a 2 a n + b 1 b 2 b m / （10 m -1）/10 n= （a 1 a 2 a n ）*（10 m -1）+ （b 1 b 2 b m ）/ （10 m -1）*10 n ） 至此， 便可以得到任意一个有限小数或无限循环小数的分数表示， 但是此时 分母未必是最简的，接下来的任务就是让分母最小，即对分子和分母进行约分，写书评，赢取编程之美- 微软技术 面试心得 这个相对比较简单。 对于任意一个分数 A/B ， 可以简化为 （A /Gcd （A, B）/ （B /Gcd （A, B），其 中 Gcd 函数为求 A 和 B 的最大公约数， 这就涉及本书中的算 法（

6、2.7 节“最大公约数问题”） ， 其中有很巧妙的解法， 请读者阅读具体的章节， 这里就不再赘述。 综上所述， 先求得小数的分数表示方式， 再对其分子分母进行约分， 便能够 得到分母最小的分数表现形式。 例如，对于小数 0.3（33），根据上述方法，可以转化为分数： 0.3（33） = （3 *（10 2 -1）+ 33 ）/ （10 2 -1）*10） = （3*99+33 ）/990 = 1 / 3 对于小数 0. 285714（285714），我们也可以算出： 0. 285714（285714） = （285714 *（10 6 -1） + 285714 ） / （10 6 -1）*10 6 ） = （285714*999999 +285714 ） / 999999000000 = 285714 / 999999 = 2/7