第二章 高精度计算.doc

高精度运算所谓的高精度运算,是指参与运算的数(加数,减数,因子）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。例如，求两个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;beginwrite(input s1:);readln(s1);write(input s2:);readln(s2);读入两个数s1，s2，都是字符串类型l:=length(s1);求出s1的长度，也即s1的位数；有关字符串的知识。k1:=260;for i:=l downto 1 dobeginak1:=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 dobeginx:=a i +b i +y;c i :=x mod 10;y:=x div 10;end; if y0 then begin k:=k-1;ck:=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;beginwrite(input s1:);readln(s1);write(input s2:);readln(s2);l:=length(s1);k1:=260;for i:=l downto 1 dobeginak1:=ord(s1 i )-48;k1:=k1-1; end; k1:=k1+1;l:=length(s2);k2:=260;for i:=l downto 1 dobeginbk2:=ord(s2 i )-48;k2:=k2-1; end; k2:=k2+1; if k1k2 then k:=k2 else k:=k1;y:=0;for i:=260 downto k dobeginx:=a i +b i +y;c i :=x mod 10;y:=x div 10;end;if y0 then begin k:=k-1;ck:=y; end;for i:=k to 260 do write(c i );writeln; end. 优化：以上的方法的有明显的缺点：（1）浪费空间：一个整型变量（-3276832767）只存放一位（09）；（2）浪费时间：一次加减只处理一位；针对以上问题，我们做如下优化：一个数组元素存放四位数；（integer的最大范围是32767，5位的话可能导致出界）。具体方法：l:=length(s1);k1:=260;repeat 有关字符串的知识s:=copy(s1,l-3,4);val(s,ak1,code);k1:=k1-1; s1:=copy(s1,1,l-4);l:=l-4; until l=0;k1:=k1+1;而因为这个改进，算法要相应改变：（1）运算时：不再逢十进位，而是逢万进位（mod 10000; div 10000);（2）输出时：最高位直接输出，其余各位，要判断是否足够4位，不足部分要补0；例如：1，23，2345这样三段的数，输出时，应该是100232345而不是1234567。改进后的算法：program sum;var s1,s2 : string;a,b,c : array 1.260 of integer;i,l,k1,k2,code : integer;beginwrite(input s1:);readln(s1);write(input s2:);readln(s2);l:=length(s1);k1:=260;repeat 有关字符串的知识s:=copy(s1,l-3,4);val(s,ak1,code);k1:=k1-1; s1:=copy(s1,1,l-4);l:=l-4; until l=0;k1:=k1+1;l:=length(s2);k2:=260;repeats:=copy(s2,l-3,4);val(s,bk2,code);k2:=k2-1; s2:=copy(s2,1,l-4);l:=l-4; until l=0; k2:=k2+1; if k1k2 then k:=k1 else k:=k2;y:=0;for i:=260 downto k dobeginx:=a i +b i +y;c i :=x mod 10000;y:=x div 10000;end;if y0 then begin k:=k-1;ck:=y;end; write(ck);for i:=k+1 to 260 dobegin if c i 1000 then write(0);if c i 100 then write(0);if c i b.len then len:=a.len get the bigger length of a,b else len:=b.len; for i:=1 to len do plus from low to high begin inc(c.si,a.si+b.si); if c.si=10 then begin dec(c.si,10); inc(c.si+1); add 1 to a higher position end; end; if c.slen+10 then inc(len); c.len:=len; end; procedure main; begin Plus(x1,x2,y); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; close(output); end; begin init; main; out; end. 2. 2 高精度减法 高精度减法程序如下： program HighPrecision2_Subtract;const fn_inp=hp2.inp; fn_out=hp2.out; maxlen=100; max length of the number type hp=record len:integer; length of the number s:array1.maxlen of integer s1 is the lowest position slen is the highest position end;var x:array1.2 of hp; y:hp; x:input ; y:output positive:boolean; procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.si); end; procedure init; var st:string; j,i:integer; begin assign(input,fn_inp); reset(input); for j:=1 to 2 do begin readln(st); xj.len:=length(st); for i:=1 to xj.len do change string to HP xj.si:=ord(stxj.len+1-i)-ord(0); end; close(input); end; procedure Subtract(a,b:hp;var c:hp); c:=a-b, suppose a=b var i,len:integer; begin fillchar(c,sizeof(c),0); if a.lenb.len then len:=a.len get the bigger length of a,b else len:=b.len; for i:=1 to len do subtract from low to high begin inc(c.si,a.si-b.si); if c.si1) and (c.slen=0) do dec(len); c.len:=len; end; function Compare(const a,b:hp):integer; 1 if ab 0 if a=b -1 if ab.len then len:=a.len get the bigger length of a,b else len:=b.len; while(len0) and (a.slen=b.slen) do dec(len); find a position which have a different digit if len=0 then compare:=0 no difference else compare:=a.slen-b.slen; end; procedure main; begin if Compare(x1,x2)=10) do begin inc(c.slen+1,c.slen div 10); c.slen=c.slen mod 10; inc(len); end; while(len1) and (c.slen=0) do dec(len); c.len:=len; end; procedure main; begin Multiply(x,z,y); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; close(output); end; begin init; main; out; end.2.高精度乘一个整型数据(integer) 只需要将上述程序的hp类型定义如下即可: type hp=record len:integer length of the number s:array1.maxlen of longint s1 is the lowest position slen is the highest position end; 3.高精度乘高精度 程序如下: program HighPrecision4_Multiply2;const fn_inp=hp4.inp; fn_out=hp4.out; maxlen=100; max length of the number type hp=record len:integer; length of the number s:array1.maxlen of integer s1 is the lowest position slen is the highest position end;var x:array1.2 of hp; y:hp; x:input ; y:output procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.si); end; procedure init; var st:string; j,i:integer; begin assign(input,fn_inp); reset(input); for j:=1 to 2 do begin readln(st); xj.len:=length(st); for i:=1 to xj.len do change string to HP xj.si:=ord(stxj.len+1-i)-ord(0); end; close(input); end; procedure Multiply(a,b:hp;var c:hp); c:=a+b var i,j,len:integer; begin fillchar(c,sizeof(c),0); for i:=1 to a.len do for j:=1 to b.len do begin inc(c.si+j-1,a.si*b.sj); inc(c.si+j,c.si+j-1 div 10); c.si+j-1:=c.si+j-1 mod 10; end; len:=a.len+b.len+1; the product of a number with i digits and a number with j digits can only have at most i+j+1 digits while(len1)and(c.slen=0) do dec(len); c.len:=len; end; procedure main; begin Multiply(x1,x2,y); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; close(output); end; begin init; main; out; end.2.4 高精度除法1.高精度除以整型数据(integer);程序如下:program HighPrecision3_Multiply1;const fn_inp=hp5.inp; fn_out=hp5.out; maxlen=100; max length of the number type hp=record len:integer; length of the number s:array1.maxlen of integer s1 is the lowest position slen is the highest position end;var x,y:hp; z,w:integer; procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.si); end; procedure init; var st:string; i:integer; begin assign(input,fn_inp); reset(input); readln(st); x.len:=length(st); for i:=1 to x.len do change string to HP x.si:=ord(stx.len+1-i)-ord(0); readln(z); close(input); end; procedure Divide(a:hp;b:integer;var c:hp;var d:integer); c:=a div b ; d:=a mod b var i,len:integer; begin fillchar(c,sizeof(c),0); len:=a.len; d:=0; for i:=len downto 1 do from high to low begin d:=d*10+a.si; c.si:=d div b; d:=d mod b; end; while(len1) and (c.slen=0) do dec(len); c.len:=len; end; procedure main; begin Divide(x,z,y,w); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; writeln(w); close(output); end; begin init; main; out; end.2.高精度除以高精度程序如下:program HighPrecision4_Multiply2;const fn_inp=hp6.inp; fn_out=hp6.out; maxlen=100; max length of the number type hp=record len:integer; length of the number s:array1.maxlen of integer s1 is the lowest position slen is the highest position end;var x:array1.2 of hp; y,w:hp; x:input ; y:output procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.si); end; procedure init; var st:string; j,i:integer; begin assign(input,fn_inp); reset(input); for j:=1 to 2 do begin readln(st); xj.len:=length(st); for i:=1 to xj.len do change string to HP xj.si:=ord(stxj.len+1-i)-ord(0); end; close(input); end; procedure Subtract(a,b:hp;var c:hp); c:=a-b, suppose a=b var i,len:integer; begin fillchar(c,sizeof(c),0); if a.lenb.len then len:=a.len get the bigger length of a,b else len:=b.len; for i:=1 to len do subtract from low to high begin inc(c.si,a.si-b.si); if c.si1) and (c.slen=0) do dec(len); c.len:=len; end; function Compare(const a,b:hp):integer; 1 if ab 0 if a=b -1 if ab.len then len:=a.len get the bigger length of a,b else len:=b.len; while(len0) and (a.slen=b.slen) do dec(len); find a position which have a different digit if len=0 then compare:=0 no difference else compare:=a.slen-b.slen; end; procedure Multiply10(var a:hp); a:=a*10 var i:Integer; begin for i:=a.len downto 1 do a.si+1:=a.si; a.s1:=0; inc(a.len); while(a.len1) and (a.sa.len=0) do dec(a.len); end; procedure Divide(a,b:hp;var c,d:hp); c:=a div b ; d:=a mod b var i,j,len:integer; begin fillchar(c,sizeof(c),0); len:=a.len; fillchar(d,sizeof(d),0); d.len:=1; for i:=len downto 1 do begin Multiply10(d); d.s1:=a.si; d:=d*10+a.si c.si:=d div b ; d:=d mod b; while(d=b) do begin d:=d-b;inc(c.si) end while(compare(d,b)=0) do begin Subtract(d,b,d); inc(c.si); end; end; while(len1)and(c.slen=0) do dec(len); c.len:=len; end; procedure main; begin Divide(x1,x2,y,w); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; PrintHP(w); writeln; close(output); end; begin init; main; out; end.练 其他回答共 1 条加: var st:string; x,y:array0.101of integer; i,j,l1,l2:integer; begin write(x=); readln(st); l1:=length(st); for i:=0 to 101 do xi:=0; for i:=l1 downto 1 do xl1-i:=ord(sti)-ord(0); write(y=); readln(st); l2:=length(st); for i:=0 to 101 do yi:=0; for i:=l2 downto 1 do yl2-i:=ord(sti)-ord(0); if l1l2 then l1:=l2; for i:=0 to l1 do begin xi:=xi+yi; xi+1:=xi+1+xi div 10; xi:=xi mod 10; end; write(x+y=); j:=101; while xj=0 do j:=j-1; for i:=j downto 0 do write(xi); readln; end. 乘: var st1,st2:string; x,y:array1.200of integer; z: array1.401of integer; i,j,l1,l2,a,b,c,d:integer; begin write(x=); readln(st1); l1:=length(st1); for i:=1 to 200 do xi:=0; for i:=l1 downto 1 do xl1+1-i:=ord(st1i)-ord(0); write(y=); readln(st2); l2:=length(st2); for i:=1 to 200 do yi:=0; for i:=l2 downto 1 do yl2+1-i:=ord(st2i)-ord(0); for i:=1 to l1 do for j:=1 to l2 do begin a:=xi*yj; b:=a div 10; c:=a mod 10; d:=i+j-1;积z数组的元素号 zd:=zd+c; zd+1:=zd+1+zd div 10 + b;进位 zd:=zd mod 10; end; a:=l1+l2; while za=0 do a:=a-1; write(st1,*,st2,=); for i:=a downto 1 do write(zi); writeln; readln; end. 差: var st,st1,st2:string; x,y,z:array0.200of byte; i,k,s1,s2,code:integer; begin write(x=); readln(st1); s1:=length(st1); write(y=); readln(st2); s2:=length(st2); write(st1,-,st2,=); if (s1s2)or(s1=s2)and(st1st2) then begin write(-); st:=st1;st1:=st2;st2:=st; k:=s1;s1:=s2;s2:=k; end; fillchar(x,sizeof(x),0); fillchar(y,sizeof(y),0); fillchar(z,sizeof(z),0); for i:=1 to s1 do val(st1i,xs1+1-i,code); for i:=1 to s2 do val(st2i,ys2+1-i,code); for i:= 1 to s1 do begin if xi-yi1) and (c.slen=0) do dec(