高精度问题

一、高精度计算问题Pascal定义了五个标准整数类型，如下表所示:(举例，输出a+b,a/b)类型取值范围占字节数格式shortint（短整型）-128..1271带符号8位integer（整型）-32768..327672带符号16位longint（长整型）-2147483648..21474836474带符号32位byte（字节型）0..2551无符号8位word（字型）0..655352无符号16位在前面程序中常用的数据类型除整数类型,还有实数类型。pascal还定义了五个标准实数类型，列表所示如下:类型取值范围占字节数有效数字real2.9×10-39~1.7×103867~8位single1.5×10-45~3.4×1038411~12位double5.0×10-324~1.7×10308815~16位extended1.9×10-4951~1.1×1049321019~20位comp-9.2*1018+1~9.2*1018819~20位注:有效数字是指,超出有效位数,计算机只能按浮点形式输出.在有些试题中,变量运算对象的数值范围是任何数据类型都无法容纳的,因此人们不得不采用高精度运算.高精度运算是指:当参与运算的数范围大大超出了标准数据类型（整型，实型）能表示的范围的运算时，通过数组、字串的形式，进行适当处理的方法。&16;高精度加法1、加数、减数、运算结果的输入和存储用数组和字符串表示数据、结果。（1）数组表示：每个数组元素存储1位，有多少位就需要多少个数组元素；（优化重点）优点：每一位都是数的形式，可以直接加减；运算时非常方便缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；（2）字符串表示：字符串的最大长度是255，可以表示255位。优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；缺点：每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；（3）综合以上所述，对两种数据结构取长补短：用字符串读入数据，用数组存储数据：vars:string;{字符串最多可以表示255位}a,b,c:array[1..260]ofinteger;{定义数组存放数字}i,la,lb:integer;beginreadln(s);{读入第一个字符串}la:=length(s);{求出s的长度，也即第一个数的位数；}fori:=1tolado{将字符串的每一位字符转化为数字,并倒序存入数组a}a[i]:=ord(s[la-i+1])-ord(‘0’)readln(s);lb:=length(s);{求出s的长度，也即第二个数的位数；}fori:=1downtolbdoa[i]:=ord(s[lb-i+1])-ord(‘0’)end;2、运算过程：模拟手工计算（1）运算顺序：从低位向高位运算；先计算低位再计算高位；（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、DIV运算完成这一步；（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；（4）如果两个加数位数不一样多，则按位数多的一个进行计算；ifla=lbthenlen:=laelselen:=lb;y:=0{y表示进位,初值为0}fori:=1tolendodobeginx:=a[i]+b[i]+y;c[i]:=xmod10;y:=xdiv10;//c[i]:=a[i]+b[i]+c[i];c[i+1]:=c[i]div10;c[i]:=c[i]mod10end;ify0thenlen:=len+1;//ifc[len+1]0thenlen:=len+1;3、结果的输出（优化重点）:按运算结果的实际位数输出fori:=lendownto1dowrite(c[i]);完整程序:高精度加法programbigPlus;vara,b,c:array[1..260]ofinteger;la,lb,len,i:integer;s:string;procedureinit;beginfillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);fillchar(c,sizeof(c),0);readln(s);la:=length(s);fori:=1toladoa[la-i+1]:=ord(s[i])-ord('0');readln(s);lb:=length(s);fori:=1tolbdob[lb-i+1]:=ord(s[i])-ord('0');ifla=lbthenlen:=laelselen:=lb;end;begininit;{调用初始化过程}fori:=1tolendobeginc[i]:=a[i]+b[i]+c[i];c[i+1]:=c[i]div10;c[i]:=c[i]mod10;end;ifc[len+1]0thenlen:=len+1;fori:=lendownto1dowrite(c[i]);readln;end.4、优化：以上的方法的有明显的缺点：（1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）；（2）浪费时间：一次加减只处理一位；针对以上问题，我们做如下优化：一个数组元素存放四位数；（integer的最大范围是32767，5位的话可能导致出界）。具体方法：a.初始化过程要改变:procedureinit;beginfillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);fillchar(c,sizeof(c),0);readln(s);la:=length(s)fori:=1toladobeginj:=(la-i)div4+1;a[j]:=a[j]*10+ord(s[i])-48;end;readln(s);lb:=length(s);fori:=1tolbdobeginj:=(lb-i)div4+1;b[j]:=b[j]*10+ord(s[i])-48;end;la:=(la+3)div4;lb:=(lb+3)div4;ifla=lbthenlen:=laelselen:=lb;end;b.运算过程要改变mod10000div10000c.输出要改变:ifc[len+1]0thenlen:=len+1;write(c[len]);fori:=len-1downto1dobeginifc[i]1000thenwrite(‘0’);ifc[i]100thenwrite(‘0’);ifc[i]10thenwrite(‘0’);write(c[i]);end;算法要相应改变：（1）运算时：不再逢十进位，而是逢万进位（mod10000;div10000);（2）输出时：最高位直接输出，其余各位，要判断是否足够4位，不足部分要补0；例如：1，23，2345这样三段的数，输出时，应该是100232345而不是1234567。&16;高精度减法1、和高精度加法相比，减法在差为负数时处理的细节更多一点：当被减数小于减数时，差为负数，差的绝对值是减数减去被减数；在程序实现上用一个变量来存储符号位，用另一个数组存差的绝对值。2、算法流程：（1）读入两个字符串S1，S2（字符串）；（2）置符号位：判断被减数是否大于减数：大则将符号位置为空；小则将符号位置为“-”，交换减数与被减数；（3）被减数与减数处理成数值，放在数组中；（4）运算：A、取数；B、判断是否需要借位；C、减，将运算结果放到差数组相应位中；D、判断是否运算完成：是，转5；不是，转A；（5）打印结果：符号位，第1位，循环处理第2到最后一位；3、细化：（1）如何判断被减数与减数的大小：{首先将两个字符串的位数补成一样(因为字符串的比较是从左边对齐的；两个字符串一样长才能真正地比较出大小)：短的在左边补0}la:=length(s1);lb:=length(s2);iflalbthenfori:=1tola-lbdos2:='0'+s2elsefori:=1tolb-lados1:='0'+s1;{接着比较大小：直接比较字符串大小，s1存被减数，fh存符号}fh:='';ifs1s2thenbeginfh:='-';s:=s1;s1:=s2;s2:=s;end;（2）将字符串处理成数值：la:=length(s1);{求出s1的长度，也即s1的位数。}fori:=ltoladoa[la-i+1]:=ord(s1[i])-48;{将字符转成数值并倒序放入数组a}字符串s2的处理方法同上（3）打印结果：去掉结果中多余的0完整程序:高精度减法(未优化,优化方法参照加法的优化)programbigminus;vara,b,c:array[1..260]ofinteger;la,lb,len,i:integer;s1,s2:string;procedureinit;beginfillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);readln(s1);readln(s2);la:=length(s1);lb:=length(s2);iflalbthenfori:=1tola-lbdos2:='0'+s2elsefori:=1tolb-lados1:='0'+s1;ifs1s2thenbegins:=s1;s1:=s2;s2:=s;write('-');end;ifla=lbthenlen:=laelselen:=lb;fori:=1tolendoa[len-i+1]:=ord(s[i])-ord('0');fori:=1tolendob[len-i+1]:=ord(s[i])-ord('0');end;begininit;{调用初始化过程}fori:=1tolendobeginc[i]:=a[i]-b[i]+c[i];ifc[i]0thenbeginc[i]:=c[i]+10;c[i+1]:=c[i+1]-1;end;end;while(len1)and(c[len]=0)thenlen:=len-1;{调整长度,输出时去掉多余的0}fori:=lendownto1dowrite(c[i]);readln;end.高精度乘法:(1)高精度乘以低精度(2)高精度乘以高精度高精度运算的过程汇总:高精度数的定义：typehp=array[1..maxlen]ofinteger;1．高精度加法procedureplus(a,b:hp;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);ifa[0]b[0]thenlen:=a[0]elselen:=b[0];fori:=1tolendobegininc(c[i],a[i]+b[i]);ifc[i]10thenbegindec(c[i],10);inc(c[i+1]);end;{进位}end;ifc[len+1]0theninc(len);c[0]:=len;end;{plus}2．高精度减法proceduresubstract(a,b:hp;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);ifa[0]b[0]thenlen:=a[0]elselen:=b[0];fori:=1tolendobegininc(c[i],a[i]-b[i]);ifc[i]0thenbegininc(c[i],10);dec(c[i+1]);end;while(len1)and(c[len]=0)dodec(len);c[0]:=len;end;3．高精度乘以低精度proceduremultiply(a:hp;b:longint;varc:hp);vari,len:integer