第二章高精度整数的算法

《第二章高精度整数的算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章、高精度运算数据结构加法运算减法运算乘法（高精度*单精度）乘法（高精度*高精度）算法的评价改善高精度运算的效率Pascal语言的常用数据类型C++常用基本类型问题的提出程序设计语言所处理加工的各类数据都有相应的值域限定，一旦某类型的数据超出了规定的范围，运算结果就会出错。但是在有些试题中，变量运算对象的数值范围是任何数据类型所载法容纳的，因此人们不得不采用高精度运算。数据结构由于待处理的数据超过了任何一种数据类型所能容纳的范围，因此必须采用数字串的形式输入，并将其转化为整数数组。该数组的每一个元素对应一位十进制数，由其下标顺序指明位序号。运算规则如同算术运算。由于高精度运算的结

2、果可能使得数据长度发生增减，因此除需要用整数数组存储数据外，还需要用一个整数变量记录整数数组的元素个数，即数据的实际长度。C语言描述#defineMAXLEN10000typedefstruct{intlen;/*长度*/ints[MAXLEN];/*表示整数的数组*/}Integer;Integera,b;C++语言描述constintMAXLEN=10000;classInteger{public:intlen;//长度ints[MAXLEN];//表示整数的数组};Integera,b;将数字串转化为整数数组a的方法如下：Char[MAXLEN]s;cin>>s;a.len=s

3、trlen(s);for(inti=0;i

4、erc;//保存返回值intlen=a.len>b.len?a.len:b.len;//确定最大位数for(inti=0;i<=len;i++)c.s[i]=0;//C各位清0for(i=0;i=10){c.s[i]-=10;//调整进位c.s[i+1]++;}//调整当前位}if(c.s[len]>0)len++;//调整结果长度c.len=len;returnc;}说明C各位清0：for(inti=0;i<=len;i++)c.s[i]=0;也可以用memset()函数memset(

5、c.s,0,len);三、减法运算c=a-b(a,b,c为Integer类型,a>b)1.依照由低位至高位（第0位至第len-1位）的顺序进行减法运算。2.在每一次按位运算中，若出现不够减的情况(a.s[i]b>0Integerc;intlen=a.len;for(inti=0;i

6、for(i=0;i1)&&(c.s[len]==0))len--;c.len=len;returnc;}四、乘法（高精度*单精度）c=a*b(a,c为Integer,b为int)按照乘法规则，从a的第0位开始逐位与b相乘。在第i位乘法运算中（0<=i<=a.len-1),a的i位与b的乘积必须加上i-1位的进位(i-1位的乘积除以10的整商)，然后规整积的i位（取i位的乘积对10的余数）。Integermul1(constIn

7、teger&a,intb){Integerc;intlen=a.len;for(inti=0;i=10)){c.s[len]+=c.s[len-1]/10;c.s[len-1]=c.s[len-1]%10;len++;}whil