当前位置:Gxlcms > mysql > 【编程之美】2.6精确表达浮点数

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

时间:2021-07-01 10:21:17 帮助过:32人阅读

【问题描述】: 在计算机中,使用float或者double来存储小数是不能得到精确的。如果你希望得到精确计算结果,最好是用分数形式来表示小数。有限小数或者无限循环小数都可以转化为分数。比如: 0.9 = 9/10 0.333(3)= 1/3(括号中的数字表示是循环节) 当然


【问题描述】:

在计算机中,使用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.a1a2an,要么为无限循环小数X=0.a1a2anb1b2bm),X表示式中的字母a1a2anb1b2bm都是0~9的数字,括号部分(b1b2bm)表示循环节,我们需要处理的就是以上两种情况。

对于有限小数X=0.a1a2an来说,这个问题比较简单,X就等于(a1a2an/10n

对于无限循环小数X=0.a1a2anb1b2bm)来说,其复杂部分在于小数点后同时有非循环部分和循环部分,我们可以做如下的转换:

X= 0.a1a2anb1b2bm

10n* X= a1a2an.b1b2bm

10n* X= a1a2an+0.b1b2bm

X =a1a2an+0.b1b2bm))/10n

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

Y=0. b1b2bm,那么

10m *Y=b1b2bm.b1b2bm

10m *Y=b1b2bm+0.b1b2bm

10m *Y-Y=b1b2bm

Y= b1b2bm/10m-1

Y代入前面的X的等式可得:

X=a1a2an+Y/10n

=a1a2an+ b1b2bm/10m-1))/10n

=((a1a2an*10m-1+b1b2bm))/((10m-1*10n

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

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

例如,对于小数0.333),根据上述方法,可以转化为分数:

0.333

=3 *102-1+ 33/((102-1*10

=3*99+33/990

= 1 / 3

对于小数0. 285714285714),我们也可以算出:

0. 285714285714

= 285714 *106-1+ 285714/ ((106-1*106

= 285714*999999 +285714/ 999999000000

= 285714 / 999999

= 2/7


以下给出代码,简单实现:

  1. void Cal(char* str)
  2. {
  3. char *p=str;
  4. char *q=str,*q1=str;//q和q1分别存储(和)的指针
  5. while(*p!='\0')
  6. {
  7. if(*p=='(')
  8. {
  9. q=p;
  10. }
  11. if(*p==')')
  12. {
  13. q1=p;
  14. }
  15. p++;
  16. }
  17. if(q==q1)
  18. {
  19. cout<<"有限小数"<<endl; p="str+2;" char="" *t="(char*)malloc(sizeof(char)*(strlen(str)-1));" memset(t,0,sizeof(char)*(strlen(str)-1));="" int="" i="0;" while(i<strlen(str)-1)="" {="" *(t+i++)="*p++;" }="" cout<<br="">
  20. <br>
  21. <p><span>为了更完善,分两种情况:</span></p>
  22. <p><span>1、对于小数的情况,不用定义数组形式:</span></p>
  23. <p></p><pre class="brush:php;toolbar:false layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li>#include <iostream></li><li>using namespace std;</li><li>long long gcd(long long a, long long b)</li><li>{</li><li>if (a < b)</li><li>{</li><li>long long tmp = a;</li><li>a = b;</li><li>b = tmp;</li><li>}</li><li>int i, k=0;</li><li>while (b!=0)</li><li>{</li><li>if ((a&1) == 0)</li><li>{</li><li>if ((b&1) == 0)</li><li>{</li><li>// a,b均是偶数,f(a,b)=2*f(a>>1,b>>1)</li><li>a >>= 1;</li><li>b >>= 1;</li><li>k++;</li><li>}</li><li>else</li><li>// a为偶数,b为奇数,f(a,b)=f(a>>1,b)</li><li>a >>= 1;</li><li>}</li><li>else</li><li>{</li><li>if ((b&1) == 0)</li><li>// a为奇数,b为偶数,f(a,b)=f(a,b>>1)</li><li>b >>= 1;</li><li>else</li><li>// a,b均是奇数,f(a,b)=f(a-b,b)</li><li>a = a-b;</li><li>}</li><li>if (a < b)</li><li>{</li><li>long long tmp = a;</li><li>a = b;</li><li>b = tmp;</li><li>}</li><li>}</li><li>return a << k;</li><li>}</li><li>int main()</li><li>{</li><li>long long a=0, b=0, c=0;</li><li>// 整数部分c,非循环小数a,循环小数b</li><li>scanf("%d.%d(%d)",&c, &a, &b);</li><li>if (a==0 && b==0)</li><li>cout << c;</li><li>else</li><li>{</li><li>// 分子up,分母down</li><li>long long up = c;</li><li>long long down = 1;</li><li>long long ta = a;</li><li>while (ta)</li><li>{</li><li>down *= 10;</li><li>ta /= 10;</li><li>}</li><li>up = c*down+a;</li><li>if (b!=0)</li><li>{</li><li>long long wb = 1;</li><li>long long tb = b;</li><li>while (tb)</li><li>{</li><li>wb *= 10;</li><li>tb /= 10;</li><li>}</li><li>up = up*(wb-1)+b;</li><li>down = down*(wb-1);</li><li>}</li><li>long long fac = gcd(up, down);</li><li>cout << up/fac << "/" << down/fac << endl;</li><li>}</li><li>}</iostream></li></ol></pre><br>
  24. <br>
  25. <p></p>
  26. <p><span>2、<span>用于大整数,定义了大整数类型,以及对应的加减乘除、比较移位运算</span></span></p>
  27. <p></p><pre class="brush:php;toolbar:false layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol" style="margin-left: 1px;"><li>#include <iostream></li><li>#include <cstring></li><li>#include <string></li><li>using namespace std;</li><li>// 大整数类型</li><li>#define MAXLEN 1000</li><li>struct HP {int len, s[MAXLEN];};</li><li>void PrintHP(HP x) </li><li>{</li><li>for (int i=x.len; i>=1; i--)</li><li>cout << x.s[i];</li><li>}</li><li>// 字符串转大整数</li><li>void Str2HP(const char *s, HP &x)</li><li>{</li><li>x.len = strlen(s);</li><li>for (int i=1; i<=x.len; i++)</li><li>x.s[i] = s[x.len-i] - '0';</li><li>if (x.len == 0)</li><li>{</li><li>x.len = 1;</li><li>x.s[1] = 0;</li><li>}</li><li>}</li><li>// 大整数的加法</li><li>void Plus(const HP a, const HP b, HP &c)</li><li>{</li><li>int i; c.s[1] = 0;</li><li>// 大整数a,b的加法操作和结果c的进位操作</li><li>for (i=1; i<=a.len || i<=b.len || c.s[i]; i++)</li><li>{</li><li>if (i <= a.len) c.s[i] += a.s[i];</li><li>if (i <= b.len) c.s[i] += b.s[i];</li><li>c.s[i+1] = c.s[i]/10; c.s[i] %= 10;</li><li>}</li><li>// 退出循环到原因是c.s[i]==0,所以取前一位</li><li>c.len = i-1; </li><li>if (c.len == 0) c.len = 1;</li><li>}</li><li>// 大整数的减法</li><li>void Subtract(const HP a, const HP b, HP &c)</li><li>{</li><li>int i, j;</li><li>for (i=1,j=0; i<=a.len; i++)</li><li>{</li><li>// j表示是否要对高位进行借位</li><li>c.s[i] = a.s[i] - j;</li><li>if (i <= b.len) c.s[i] -= b.s[i];</li><li>if (c.s[i] < 0) </li><li>{</li><li>// 向高位借位,补10</li><li>j = 1;</li><li>c.s[i] += 10;</li><li>}</li><li>else j = 0;</li><li>}</li><li>c.len = a.len;</li><li>while (c.len > 1 && !c.s[c.len]) c.len--;</li><li>}</li><li>// 大整数的比较</li><li>int HPCompare(const HP &x, const HP &y)</li><li>{</li><li>if (x.len > y.len) return 1;</li><li>if (x.len < y.len) return -1;</li><li>int i = x.len;</li><li>while (i>1 && (x.s[i]==y.s[i])) i--;</li><li>return x.s[i] - y.s[i];</li><li>}</li><li>// 大整数的乘法</li><li>void Multi(const HP a, const HP b, HP &c)</li><li>{</li><li>int i, j;</li><li>// 对乘法结果赋初值,以方便之后的+=运算</li><li>c.len = a.len + b.len;</li><li>for (i=1; i<=c.len; i++) c.s[i] = 0;</li><li>for (i=1; i<=a.len; i++)</li><li>for (j=1; j<=b.len; j++)</li><li>c.s[i+j-1] += a.s[i]*b.s[j];</li><li>// 运算结果进位</li><li>for (i=1; i<c.len; i++)="" {c.s[i+1]="" +="c.s[i]/10;" c.s[i]="" %="10;}" 最高位继续进位="" while="" (c.s[i])="" i++;}="" 确保最高位不为0="" (i="">1 && !c.s[i]) i--;</li><li>c.len = i;</li><li>}</li><li>// 大整数的除法</li><li>void Divide(const HP a, const HP b, HP &c, HP &d)</li><li>{</li><li>int i, j;</li><li>// 用余数d存被除数a的前i位数据,用来多次减去除数b,以得到商c</li><li>d.len = 1; d.s[1] = 0;</li><li>for (i=a.len; i>0; i--)</li><li>{</li><li>if (!(d.len == 1 && d.s[1] == 0))</li><li>{</li><li>// i没移一位,余数d也移位</li><li>for (j=d.len; j>0; j--)</li><li>d.s[j+1] = d.s[j];</li><li>d.len++;</li><li>}</li><li>d.s[1] = a.s[i];</li><li>c.s[i] = 0;</li><li>// 余数d大于除数b时,才可以进行减操作</li><li>while ((j=HPCompare(d,b)) >= 0)</li><li>{</li><li>Subtract(d, b, d);</li><li>c.s[i]++;</li><li>if (j == 0) break;</li><li>}</li><li>}</li><li>c.len = a.len;</li><li>while (c.len > 1 && c.s[c.len] == 0)</li><li>c.len--;</li><li>}</li><li>// 十进位右移</li><li>void RightShift(HP &x, int k)</li><li>{</li><li>for (int i=1; i<=x.len-k; i++)</li><li>x.s[i] = x.s[i+k];</li><li>x.len -= k;</li><li>if(x.len <= 0)</li><li>{</li><li>x.len = 1;</li><li>x.s[1] = 0;</li><li>}</li><li>}</li><li>// 十进位左移</li><li>void LeftShift(HP &x, int k)</li><li>{</li><li>int i;</li><li>for (i=x.len; i>=1; i--)</li><li>x.s[i+k] = x.s[i];</li><li>for (i=k; i>=1; i--)</li><li>x.s[i] = 0;</li><li>x.len += k;</li><li>}</li><li>// 求大整数的最大公约数</li><li>void GCD(HP a, HP b, HP &c)</li><li>{</li><li>if (b.len == 1 && b.s[1] == 0)</li><li>{</li><li>c.len = a.len;</li><li>memcpy(c.s, a.s, (a.len+1)*sizeof(int));</li><li>}</li><li>else</li><li>{</li><li>HP m, n;</li><li>Divide(a, b, m, n);</li><li>GCD(b, n, c);</li><li>}</li><li>}</li><li>int main()</li><li>{</li><li>string str;</li><li>string strc, stra, strb;</li><li>cin >> str;</li><li>int posc = str.find('.');</li><li>int posa = str.find('(');</li><li>int posb = str.find(')');</li><li>strc = str.substr(0, posc);</li><li>if (posc < 0)</li><li>cout << strc;</li><li>else</li><li>{</li><li>HP a, b, c;</li><li>HP tmp; tmp.len = 1; tmp.s[1] = 1;</li><li>// 整数部分</li><li>Str2HP(strc.c_str(), c);</li><li>stra = str.substr(posc+1, posa-posc-1);</li><li>// 非循环部分</li><li>Str2HP(stra.c_str(), a);</li><li>// up分子,down分母</li><li>HP up = c, down = tmp;</li><li>// 乘以10^|a|</li><li>LeftShift(down, stra.size());</li><li>LeftShift(up, stra.size());</li><li>Plus(up, a, up);</li><li>if (posa >= 0)</li><li>{</li><li>strb = str.substr(posa+1, posb-posa-1);</li><li>// 循环部分</li><li>Str2HP(strb.c_str(), b);</li><li>HP m = tmp;</li><li>LeftShift(m, strb.size());</li><li>Subtract(m, tmp, m);</li><li>// 乘以10^(|b|-1)</li><li>Multi(up, m, up);</li><li>Plus(up, b, up);</li><li>Multi(down, m, down);</li><li>}</li><li>// 求分子分母的最大公约数</li><li>GCD(down, up, tmp);</li><li>HP h;</li><li>Divide(down, tmp, down, h);</li><li>Divide(up, tmp, up, h);</li><li>PrintHP(up); cout << "/";</li><li>PrintHP(down); cout << endl;</li><li>}</li><li>}</li><li></c.len;></string></cstring></iostream></li></ol></pre> </endl;>

人气教程排行