写书评,赢取《编程之美--微软技术面试心得》www.ieee.org.cn/BCZM.asp
精确
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
达浮点数
在计算机中,使用 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)、……
写书评,赢取《编程之美--微软技术面试心得》www.ieee.org.cn/BCZM.asp
分析与解法
拿到这样一个问题,我们往往会从最简单的情况入手,因为所有的小数都可
以分解成一个整数和一个纯小数之和,不妨只考虑大于 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)
至此,便可以得到任意一个有限小数或无限循环小数的分数表示,但是此时
分母未必是最简的,接下来的任务就是让分母最小,即对分子和分母进行约分,
写书评,赢取《编程之美--微软技术面试心得》www.ieee.org.cn/BCZM.asp
这个相对比较简单。对于任意一个分数 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