高精度运算问题.doc

高精度运算问题高精度运算，是指参与运算的数(加数,减数,因子）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高精度算法了。Java 提供了两个类专门用于进行高精度运算BigInteger 和 BigDecimal ，尽管它们可大致划分到与封装器相同的类别里，但两者都没有对应的主类型；这两个类都有自己的一系列方法，类似于我们针对主类型执行的操作，也就是说能用int 或float 做的事情，用BigInteger和BigDecimal 一样可以做，只是必须换用方法调用，而不是使用运算符。此外由于牵涉更多，所以运算速度会慢一点总之我们牺牲了速度，但换来了精度。1.1高精度浮点数BigDecimal一些非整数值（如几美元和几美分这样的小数）需要很精确。浮点数不是精确值，所以使用它们会导致舍入误差。因此，使用浮点数来试图表示象货币量这样的精确数量不是一个好的想法。使用浮点数来进行美元和美分计算会得到灾难性的后果。浮点数最好用来表示象测量值这类数值，这类值从一开始就不怎么精确。 从 JDK 1.3 起，Java 开发人员就有了另一种数值表示法来表示非整数：BigDecimal。BigDecimal 是标准的类，在编译器中不需要特殊支持，它可以表示任意精度的小数，并对它们进行计算。在内部，可以用任意精度任何范围的值和一个换算因子来表示 BigDecimal，换算因子表示左移小数点多少位，从而得到所期望范围内的值。因此，用 BigDecimal 表示的数的形式为 unscaledValue*10-scale。用于加、减、乘和除的方法给 BigDecimal 值提供了算术运算。由于 BigDecimal 对象是不可变的，这些方法中的每一个都会产生新的 BigDecimal 对象。因此，因为创建对象的开销，BigDecimal 不适合于大量的数学计算，但设计它的目的是用来精确地表示小数。如果您正在寻找一种能精确表示如货币量这样的数值，则 BigDecimal 可以很好地胜任该任务。如浮点类型一样，BigDecimal 也有一些令人奇怪的行为。尤其在使用 equals() 方法来检测数值之间是否相等时要小心。equals() 方法认为，两个表示同一个数但换算值不同（例如，100.00 和 100.000）的 BigDecimal 值是不相等的。然而，compareTo() 方法会认为这两个数是相等的，所以在从数值上比较两个 BigDecimal 值时，应该使用 compareTo() 而不是 equals()。1.2 高精度整数BigIntegerBigInteger支持任意精度的整数，也就是说我们可精确表示任意大小的整数值；同时在运算过程中不会丢失任何信息;在BigInteger类中有所有的基本算术运算方法，如加、减、乘、除，以及可能会用到的位运算如或、异或、非、左移、右移等。高精度加法:#include#includeint lena,lenb,lenc;void plus(int a,int b,int c)/高精度加法 a+b=cint i,j,len;if(lenalenb)len=lena;else len=lenb;for(i=0;i=10)ci+1+;ci%=10;if(clen0)len+;lenc=len;int main()int i,j;char sa1000,sb1000;int a1000,b1000,c1000;while(scanf(%s%s,sa,sb)!=EOF)memset(c,0,sizeof(c);memset(a,0,sizeof(a);memset(b,0,sizeof(b);lena=strlen(sa);lenb=strlen(sb);for(j=0,i=lena-1;i=0;i-) /倒置 aj+=sai-48;for(j=0,i=lenb-1;i=0;i-)bj+=sbi-48;plus(a,b,c);for(i=lenc-1;i=0;i-)printf(%d,ci);printf(n);return 0;高精度实数加法:#include#includevoid plus(int a,int b,int c,int *len,int m)/高精度加法 a+b=cint i,l,p;l=*len;p=m;if(p=0)for(i=0;i=10)ci+1+;ci%=10;elsefor(i=0;i=10)if(i+1=p)ci+2+;else ci+1+;ci%=10;if(cl0)l+;*len=l;int main()int i,j,k,n,n1,n2,m,m1,m2,flag,point;int lena,lenb,lenc,len;int a1000,b1000,c1000;char sa1000,sb1000;while(scanf(%s%s,sa,sb)!=EOF)memset(a,0,sizeof(a);memset(b,0,sizeof(b);memset(c,0,sizeof(c);flag=0;m1=0;m2=0;point=0;n1=strlen(sa);n2=strlen(sb);for(k=n1-1;k=0;k-) /对阶n=n1-1-k;if(sak=.)an=sak;m1=n;else an=sak-48;for(k=n2-1;k=0;k-)n=n2-1-k;if(sbk=.)bn=sbk;m2=n;else bn=sbk-48;if(m1m2)flag=1;m=m1-m2;point=m1;else if(m1n2-m2)n=n1-m1;else n=n2-m2;if(flag=1) /移位for(i=n2-1;i=0;i-)bi+m=bi;for(i=0;i=0;i-)ai+m=ai;for(i=0;in2)len=n1;else len=n2;plus(a,b,c,&len,point);for(j=0;j=j;i-)if(ci=.)printf(%c,ci);else printf(%d,ci);printf(n);return 0;24点扑克游戏13.1 游戏描述“24点扑克牌游戏”是一个很多人从小到大都在玩的游戏，作为老少皆宜的大众游戏，很多人都将它作为孩子学习数学和开发智力的工具。最初是几个人使用一副扑克牌来玩此游戏，基本的游戏规则是：随便从一副扑克牌中拿出四张牌，参与游戏的人将这四张扑克牌上的数字（其中J算11、Q算12、K算13）用加、减、乘、除、四则运算（包括括号）将四个数组成一个表达式，使表达式的结果为24。看谁算得最快，谁就赢了。使用计算机模拟该游戏，就是随机产生4个113之间的整数，由用户输入它们组合后的表达式，计算机计算该表达式的值，判断是否为24。13.2 游戏解析知道了游戏的基本规则，下面开始分析设计了。大家都知道，我们直接通过键盘输入算术表达式，计算机系统是不会给我们算出表达式的结果的。那么，如何计算出表达式的值呢? 经过分析，实现这个游戏有两个关键点，一个是如何处理用户输入的表达式，以便为计算表达式的值作准备，另外一个就是对表达式如何求值。13.2.1 处理用户输入得表达式现在，将我们平时输入的表达式称为中缀表达式，而计算机存储一般都是后缀表达式。所以，我们要将用户输入的中缀表达式转换为后缀表达式后存储。1算术表达式的形式2将中缀表达式转换为后缀表达式13.2.2 对后缀表达式求值由于后缀表达式中没有括号，不需判别优先级，计算严格从左向右进行，故计算一个后缀表达式要比计算机一个中缀表达式简单得多。在我们的程序中就是对转换成的后缀表达式进行计算，这样比较方便。对后缀表达式进行求值计算的算法思想是：（1）建立一个栈（STACK类型）；（2）从左到右读后缀表达式，读到数字就将它转换为数值压入栈中，读到运算符则从栈中依次弹出两个数分别到num2和num1，然后以“num1 运算符 num2”的形式计算出结果，再将结果压加栈中；（3）如果后缀表达式未读完，就重复上面过程（2），直到读到结束符“0”为止，最后输出栈顶的数值则为最后表达式的结果。13.3 两个重要函数的实现通过前面的分析，那么下面如何具体的用C语言实现将中缀表达式转换为后缀表达式的和对后缀表达式进行求值计算的这两个函数呢？13.4 “24点扑克牌游戏”的实现两个重要算法实现了，那么“24点扑克牌游戏”的实现基本就没有太大问题了。但是为了更好的体现游戏并实现其功能，还要有几部分辅助的函数。13.4.1 栈的基本操作函数的实现在代码13-1和代码13-2中，大量的用到了栈的相关操作，所以还要在程序中编写相应的函数来实现栈的操作。由于栈的操作都是在一端进行，所以本程序实现栈的存储使用了动态存储的链表形式。我们可以将链表的表头作为栈顶，这样不但可以利用链表头指针就可以很方便实现栈的操作，还有利于空间的合理分配。栈的基本操作主要有判断栈是否为空、入栈、出栈、读取栈顶元素的值和读取栈顶元素的值并出栈。13.4.2 随机发四张扑克牌函数的实现游戏的玩法在实际中是随便发四张扑克牌，根据这四张牌上的数进行加减乘除运算结果凑成24。我们编写的程序要模拟发牌的过程，这如何解决？很简单，只需要要计算机随机产生四个113之间（扑克牌上的数是113之间）的整数即可。在C语言中，使用random函数就可产生一个随机数。13.4.3 检查输入表达式的正确性函数的实现由于对用户输入的表达式有特殊的要求（在每个数字结束后要加一个“.”），也为了程序的完整性和安全性，在程序中编写了检查用户输入的表达式是否符合要求的函数。这个程序实现使用穷举的方法，将所有可能的排列穷举出来，最后将每个排列中计算出结果。计算结果时，将前两个作为一组、后两个数作为一组，分别计算出各组的结果，再对获得的两个组结果进行计算。由于是排列，分前后两组进行计算就可满足所有可能的计算。1. publicstaticdoubleadd(doublev1,doublev2) 2. publicstaticdoublesub(doublev1,doublev2) 3. publicstaticdoublemul(doublev1,doublev2) 4. publicstaticdoublediv(doublev1,doublev2) 5. publicstaticdoublediv(doublev1,doublev2,intscale) 6. publicstaticdoubleround(doublev,intscale) 7. 附录 8. 源文件Arith.java： 9. importjava.math.BigDecimal; 10. /* 11. *由于Java的简单类型不能够精确的对浮点数进行运算，这个工具类提供精 12. *确的浮点数运算，包括加减乘除和四舍五入。 13. */14. publicclassArith/默认除法运算精度 15. privatestaticfinalintDEF_DIV_SCALE=10;/这个类不能实例化 16. privateArith() 17. 18. /* 19. *提供精确的加法运算。 20. *paramv1被加数 21. *paramv2加数 22. *return两个参数的和 23. */24. publicstaticdoubleadd(doublev1,doublev2) 25. BigDecimalb1=newBigDecimal(Double.toString(v1); 26. BigDecimalb2=newBigDecimal(Double.toString(v2); 27. returnb1.add(b2).doubleValue(); 28. 29. /* 30. *提供精确的减法运算。 31. *paramv1被减数 32. *paramv2减数 33. *return两个参数的差 34. */35. publicstaticdoublesub(doublev1,doublev2) 36. BigDecimalb1=newBigDecimal(Double.toString(v1); 37. BigDecimalb2=newBigDecimal(Double.toString(v2); 38. returnb1.subtract(b2).doubleValue(); 39. 40. /* 41. *提供精确的乘法运算。 42. *paramv1被乘数 43. *paramv2乘数 44. *return两个参数的积 45. */46. publicstaticdoublemul(doublev1,doublev2) 47. BigDecimalb1=newBigDecimal(Double.toString(v1); 48. BigDecimalb2=newBigDecimal(Double.toString(v2); 49. returnb1.multiply(b2).doubleValue(); 50. 51. /* 52. *提供（相对）精确的除法运算，当发生除不尽的情况时，精确到 53. *小数点以后10位，以后的数字四舍五入。 54. *paramv1被除数 55. *paramv2除数 56. *return两个参数的商 57. */58. publicstaticdoublediv(doublev1,doublev2) 59. returndiv(v1,v2,DEF_DIV_SCALE); 60. 61. /* 62. *提供（相对）精确的除法运算。当发生除不尽的情况时，由scale参数指 63. *定精度，以后的数字四舍五入。 64. *paramv1被除数 65. *paramv2除数 66. *paramscale表示表示需要精确到小数点以后几位。 67. *return两个参数的商 68. */69. publicstaticdoublediv(doublev1,doublev2,intscale) 70. if(scale0) 71. thrownewI