资源描述:
《第二章 高精度计算》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、高精度运算所谓的高精度运算,是指参与运算的数(加数,减数,因子……)范围大大超出了标准数据类型(整型,实型)能表示的范围的运算。例如,求两个200位的数的和。这时,就要用到高精度算法了。在这里,我们先讨论高精度加法。高精度运算主要解决以下三个问题:基本方法1、加数、减数、运算结果的输入和存储运算因子超出了整型、实型能表示的范围,肯定不能直接用一个数的形式来表示。在Pascal中,能表示多个数的数据类型有两种:数组和字符串。(1)数组:每个数组元素存储1位(在优化时,这里是一个重点!),有多少位就需要多少个数组元素;用数组表示数的优点:每一位都是数的形式,
2、可以直接加减;运算时非常方便用数组表示数的缺点:数组不能直接输入;输入时每两位数之间必须有分隔符,不符合数值的输入习惯;(2)字符串:字符串的最大长度是255,可以表示255位。用字符串表示数的优点:能直接输入输出,输入时,每两位数之间不必分隔符,符合数值的输入习惯;用字符串表示数的缺点:字符串中的每一位是一个字符,不能直接进行运算,必须先将它转化为数值再进行运算;运算时非常不方便;(3)因此,综合以上所述,对上面两种数据结构取长补短:用字符串读入数据,用数组存储数据:vars1,s2:string;a,b,c:array[1..260]ofintege
3、r;i,l,k1,k2:integer;beginwrite('inputs1:');readln(s1);write('inputs2:');readln(s2);{————读入两个数s1,s2,都是字符串类型}l:=length(s1);{求出s1的长度,也即s1的位数;有关字符串的知识。}k1:=260;fori:=ldownto1dobegina[k1]:=ord(s1[i])-48;{将字符转成数值}k1:=k1-1;end;k1:=k1+1;{————以上将s1中的字符一位一位地转成数值并存在数组a中;低位在后(从第260位开始),高位在前(
4、每存完一位,k1减1)}对s2的转化过程和上面一模一样。2、运算过程在往下看之前,大家先列竖式计算35+86。注意的问题:(1)运算顺序:两个数靠右对齐;从低位向高位运算;先计算低位再计算高位;(2)运算规则:同一位的两个数相加再加上从低位来的进位,成为该位的和;这个和去掉向高位的进位就成为该位的值;如上例:3+8+1=12,向前一位进1,本位的值是2;可借助MOD、DIV运算完成这一步;(3)最后一位的进位:如果完成两个数的相加后,进位位值不为0,则应添加一位;(4)如果两个加数位数不一样多,则按位数多的一个进行计算;ifk1>k2thenk:=k1e
5、lsek:=k2;y:=0;fori:=260downtokdobeginx:=a[i]+b[i]+y;c[i]:=xmod10;y:=xdiv10;end;ify<>0thenbegink:=k-1;c[k]:=y;end;3、结果的输出(这也是优化的一个重点)按运算结果的实际位数输出fori:=kto260dowrite(c[i]);writeln;4、例子:求两个数的加法programsum;vars,s1,s2:string;a,b,c:array[1..260]ofinteger;i,l,k1,k2:integer;beginwrite('in
6、puts1:');readln(s1);write('inputs2:');readln(s2);l:=length(s1);k1:=260;fori:=ldownto1dobegina[k1]:=ord(s1[i])-48;k1:=k1-1;end;k1:=k1+1;l:=length(s2);k2:=260;fori:=ldownto1dobeginb[k2]:=ord(s2[i])-48;k2:=k2-1;end;k2:=k2+1;ifk1>k2thenk:=k2elsek:=k1;y:=0;fori:=260downtokdobeginx:=a[
7、i]+b[i]+y;c[i]:=xmod10;y:=xdiv10;end;ify<>0thenbegink:=k-1;c[k]:=y;end;fori:=kto260dowrite(c[i]);writeln;end.优化:以上的方法的有明显的缺点:(1)浪费空间:一个整型变量(-32768~32767)只存放一位(0~9);(2)浪费时间:一次加减只处理一位;针对以上问题,我们做如下优化:一个数组元素存放四位数;(integer的最大范围是32767,5位的话可能导致出界)。具体方法:l:=length(s1);k1:=260;repeat{————有
8、关字符串的知识}s:=copy(s1,l-3,4);val(s,a[k1],co