高精度计算(加法).docVIP

高精度计算（加法） 高精度加法 所谓的高精度运算,是指参与运算的数(加数,减数,因子……）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高精度算法了。在这里，我们先讨论高精度加法。高精度运算主要解决以下三个问题： 基本方法 1、加数、减数、运算结果的输入和存储运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pascal中，能表示多个数的数据类型有两种：数组和字符串。（1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；用数组表示数的优点：每一位都是数的形式，可以直接加减；运算时非常方便用数组表示数的缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯； （2）字符串：字符串的最大长度是255，可以表示255位。用字符串表示数的优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；用字符串表示数的缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便； （3）因此，综合以上所述，对上面两种数据结构取长补短：用字符串读入数据，用数组存储数据：var s1,s2:string;????a,b,c:array [1..260] of integer;????i,l,k1,k2:integer;begin???? write(input s1:);readln(s1);???? write(input s2:);readln(s2);???? {————读入两个数s1，s2，都是字符串类型}???? l:=length(s1);{求出s1的长度，也即s1的位数；有关字符串的知识。}???? k1:=260;???? for i:=l downto 1 do???? begin???? ???? a[k1]:=ord(s1[i])-48;{将字符转成数值}???? ???? k1:=k1-1; ???? end; ???? k1:=k1+1;???? {————以上将s1中的字符一位一位地转成数值并存在数组a中；低位在后（从第260位开始），高位在前（每存完一位，k1减1）} 对s2的转化过程和上面一模一样。 2、运算过程在往下看之前，大家先列竖式计算35+86。注意的问题：（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、DIV运算完成这一步；（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；（4）如果两个加数位数不一样多，则按位数多的一个进行计算；???? if k1k2 then k:=k1 else k:=k2;???? y:=0;???? for i:=260 downto k do???? begin???????? x:=a[i]+b[i]+y;???????? c[i]:=x mod 10;???????? y:=x div 10;???? end; ???? if y0 then begin k:=k-1;c[k]:=y; end; 3、结果的输出（这也是优化的一个重点）按运算结果的实际位数输出for i:=k to 260 do write(c[i]);writeln; 4、例子：求两个数的加法program sum;var s,s1,s2:string;????a,b,c:array [1..260] of integer;????i,l,k1,k2:integer;begin???? write(input s1:);readln(s1);???? write(input s2:);readln(s2);???? ??? l:=length(s1);???? k1:=260;???? for i:=l downto 1 do???? begin???? ???? a[k1]:=ord(s1[i])-48;???? ???? k1:=k1-1; ???? end; ???? k1:=k1+1; ????l:=length(s2);???? k2:=260;???? for i:=l downto 1 do???? begin???? ???? b[k2]:=ord(s2[i])-48;???? ???? k2:=k2-1; ???? end; ???? k2: